Efficient Perfect Digital Steganography

Prof. Yvo Desmedt

BT Chair of Information Security, University College London

The Crypto 2002 Hopper-Langford-von Ahn (HLvA) steganographic schemes have a very inefficient bandwidth per cover (at most 1 bit/cover). We focus on schemes that perform optimal/close to optimal in the case the covers occur only sparsely. This is often the case when using the WWW because very few web pages are updated hundreds of times per hour. Moreover (in most of our schemes) we allow for cover distributions with memory. The adversary is a passive eavesdropper. We develop schemes with perfect hiding and perfect privacy (called perfect). We present a perfect scheme which bandwidth is optimal for fixed length message encoding. We present a close to optimal perfect scheme that encrypts a variable length of the message in each cover. This scheme links steganography to Huffman trees. This allows to approach closely Anderson-Petitcolas unachievable dream. We also address Anderson-Needham-Shamir concern that secret keys stored on disks can easily be found when having access to the disk. We introduce a stego-key model, in which both the key and the ciphertext should be stego (i.e. chosen by a known distribution not necessarily uniform). We present a scheme to send binary messages.