Simple Stateless Steganography.
Leonid Reyzin, Scott Russell · IACR Cryptology ePrint Archive · 2003
Steganography is the science of hiding the very presence of a secret message within a public communication channel. In Crypto 2002, Hopper, Langford, and von Ahn proposed the first complexitytheoretic definition and constructions of stegosystems. They later pointed out a flaw in their basic construction. Their proposed fix for this flaw dramatically reduces the efficiency of the construction, because it requires the use of strong error-correcting codes. Our first contribution is to demonstrate that the construction that was thought flawed is actually often not. By carefully analyzing the severity of the flaw in their original construction, we show that it is safe to use under proper conditions—thus eliminating the need for expensive error-correction. Moreover, when such conditions do not hold, we provide an alternative fix for the flaw, which is often more efficient. In addition, we demonstrate that for memoryless channels, the construction can be used to send multiple bits statelessly (maintaining synchronized state between the sender and the recipient, as was proposed for the original construction, is particularly problematic in steganography). We provide tight bounds on the security of such an approach.