Steganography is the problem of hiding secret messages in "innocent-looking" public communication so that the presence of the secret messages cannot be detected. This paper introduces a cryptographic formalization of steganographic security in terms of computational indistinguishability from a channel, an indexed family of probability distributions on cover messages. We use cryptographic and complexity-theoretic proof techniques to show that the existence of one-way functions and the ability to sample from the channel are necessary conditions for secure steganography. We then construct a steganographic protocol, based on rejection sampling from the channel, that is provably secure and has nearly optimal bandwidth under these conditions. This is the first known example of a general provably secure steganographic protocol. We also give the first formalization of "robust" steganography, where an adversary attempts to remove any hidden messages without unduly disrupting the cover channel. We give a necessary condition on the amount of disruption the adversary is allowed in terms of a worst case measure of mutual information. We give a construction that is provably secure and computationally efficient and has nearly optimal bandwidth, assuming repeatable access to the channel distribution.
Bibliographical noteFunding Information:
The authors wish to thank Manuel Blum, Christian Cachin, Mike Reiter, Leo Reyzin, Steven Rudich, Scott Russell, and David Wagner for the helpful conversations about this work. They especially thank Lea Kissner, Tal Malkin, and Omer Reingold for pointing out an error in the proceedings version . This work was supported by the US National Science Foundation under Grants CCR-0122581, CCR-0085982, and CNS-0546162.
- Covert channels
- Provable security