Steganographic protocols enables one to "embed" covert messages into
inconspicous 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.