Most existing formal models for information hiding have not addressed steganography, but rather the more general problem of hiding information with active adversaries in watermarking and fingerprinting applications. This is different from steganography, because the existence of a hidden message is known publicly. An information-theoretic model for steganography with a passive adversary is proposed in this paper.

The approach of this paper is to view steganography with a passive adversary as a problem of hypothesis testing, because the adversary succeeds if she or he merely detects the presence of hidden information.

The example taken to illustrate this type of steganography is the famous Simmons Prisoners Problem, the same model used 20 years ago to define the subliminal channel in the authentication schemas.

The adversary’s task--of distinguishing between an innocent cover message, C, and a modified message, S, containing hidden information--is interpreted as a hypothesis testing problem. The security of a steganographic system is quantified in terms of the relative entropy between the distributions of C and S, which yields bounds on the detection capability of any adversary. A stegosystem is called perfect if this relative entropy is zero. The model is presented in section 2 of the paper.

The consequence of the security notion defined here for the detection performance of any adversary is investigated in section 3, following a brief review of the theory of hypothesis testing. Some basic bounds on this detection are obtained.

Two elementary stegosystems with information-theoretic security are described in section 4 to illustrate the definition. One conclusion is that the visual cryptography is an example of a perfectly secure stegosystem.

In section 5, a universal stegosystem is presented that requires its users to have no knowledge of the covertext distribution; it works by estimating the distribution, and then simulating a covertext by sampling a stegotext with a similar distribution. A discussion of the model, and a comparison to related work are presented in section 6, and conclusions are drawn in section 7.

It is shown that secure steganography schemes exist in this model, provided the covertext distribution satisfies certain conditions. A universal stegosystem is presented that needs no knowledge of the covertext distribution, except that it is generated from independently repeated experiments.