The Information Theory of Hidden Message

When a secret payload is concealed inside an apparently innocent cover, it is known as steganography. An ancient art, it has more recently come to the fore in cases of espionage and terrorism. It is frighteningly easy to hide large secret payloads in digital media such as pictures, audio, and video, while concealing even the existence of the secret from an enemy monitor.

In this talk I will demonstrate some simple techniques for steganography, and consider the question of capacity: how much data can be hidden, before it becomes detectable. This is a statistically well-founded question and represents an alternative to the usual channels and information theory of Shannon. I will survey work on the "Square Root Law" of capacity for steganography, which is in sharp contrast to the standard results about channel capacity. This is work with some subtle difficulties, and not all the variations are fully explored, but it seems to chime with empirical results from the detection of steganography in practice.