Efficient steganography with provable security guarantees

Steganography is the study of the art and science of information hiding. Steganographic protocols enable one to embed covert messages into inconspicuous data over a public communication channel in such a way that no one, aside from the sender and the intended receiver, can even detect the presence of the secret messages. Observe that cryptography alone cannot accomplish this goal as the transmission of an encrypted message, no matter how secure, attracts attention. While there are many ad-hoc implementations of steganography protocols, in this thesis, we design and analyze provably secure protocols for information-theoretic and complexity-theoretic steganography. We demonstrate that our protocols offer security, soundness and efficiency guarantees through rigorous analysis using tools from information theory, cryptography, probability and complexity theory. Our system is an analog of a one-time pad for steganography and can be applied in the natural complexity theoretic model using a pseudorandom generator for transmission of longer messages. In our protocol construction, we employ pseudorandom functions such as almost k-wise independent family of functions and extractors to embed messages into the communication channel, both of which are used in the design of steganographic protocols for the first time, to the best of our knowledge.