Randomness-optimal Steganography

Aggelos Kiayias, Alexander Russell, Narasimha Shashidhar

Research output: Working paper

Abstract / Description of output

Steganographic protocols enables one to “embed” covert messages into inconspicuous data over a public communication channel in such a way that no one, aside from the sender and the intended receiver can even detect the presence of the secret message. In this paper, we provide a new provably-secure, private-key steganographic encryption protocol. We prove the security of our protocol in the complexity- theoretic framework where security is quantified as the advantage (compared to a random guess) that the adversary has in distinguishing between innocent covertext and stegotext that embeds a message of his choice. The fundamental building block of our steganographic encryption protocol is a “one-time stegosystem” that allows two parties to transmit messages of length at most that of the shared key with information-theoretic security guarantees. The employment of a pseudorandom generator (PRG) permits secure 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. In this paper, we initiate the study of employing randomness extractors in a steganographic protocol construction to embed secret messages over the channel. To the best of our knowledge this is the first time randomness extractors have been applied in steganography
Original languageEnglish
Publication statusPublished - 2009


Dive into the research topics of 'Randomness-optimal Steganography'. Together they form a unique fingerprint.

Cite this