Efficient Steganography with Provable Security Guarantees

Aggelos Kiayias, Yona Raekow, Alexander Russell

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We provide a new provably-secure steganographic encryption protocol that is proven secure in the complexity-theoretic framework of Hopper et al. The fundamental building block of our steganographic encryption protocol is a “one-time stegosystem” that allows two parties to transmit one-time steganographic messages of length shorter than the shared key with information-theoretic security guarantees. The employment of a pseudorandom number generator (PRNG) allows the transmission of longer messages in the same way that such a generator allows the use of one-time pad encryption for messages longer than the key in symmetric encryption. The advantage of our construction compared to that of Hopper et al. is that it avoids the use of a pseudorandom function family and instead relies (directly) on a PRNG in a way that provides a linear versus constant improvement in the number of applications of the underlying (say) one-way permutation per bit transmitted. This advantageous trade-off is achieved by substituting the pseudorandom function family employed in the previous construction with an appropriate combinatorial construction that has been used extensively in derandomization, namely almost t-wise independent function families.
Original languageEnglish
Title of host publicationInformation Hiding, 7th International Workshop, IH 2005, Barcelona, Spain, June 6-8, 2005, Revised Selected Papers
PublisherSpringer Berlin Heidelberg
Number of pages13
ISBN (Electronic)978-3-540-31481-3
ISBN (Print)978-3-540-29039-1
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science (LNCS)
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743


Dive into the research topics of 'Efficient Steganography with Provable Security Guarantees'. Together they form a unique fingerprint.

Cite this