Upper and Lower Bounds on Black-Box Steganography

Nenad Dedic; Gene Itkis; Leonid Reyzin; Scott Russell

Paper 2004/246

Upper and Lower Bounds on Black-Box Steganography

Nenad Dedic, Gene Itkis, Leonid Reyzin, and Scott Russell

Abstract

We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).

Note: This paper incorporates and supersedes report 2003/093. Extended abstract of this paper appears at TCC 2005. This is the full version, to appear in the Journal of Cryptology (Feb. 29 2008 revision clarifies the lowerbound proof and makes other, minor, changes; Jun 4 2008 revision corrects typos).

Metadata

Available format(s): PDF PS
Publication info: Published elsewhere. Unknown where it was published
Keywords: steganography covert communication rejection sampling lower bound pseudorandomnness information hiding huge random objects
Contact author(s): reyzin @ cs bu edu
History: 2008-06-04: last of 6 revisions; 2004-09-22: received; See all versions
Short URL: https://ia.cr/2004/246
License: CC BY

BibTeX

@misc{cryptoeprint:2004/246,
      author = {Nenad Dedic and Gene Itkis and Leonid Reyzin and Scott Russell},
      title = {Upper and Lower Bounds on Black-Box Steganography},
      howpublished = {Cryptology ePrint Archive, Paper 2004/246},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/246}},
      url = {https://eprint.iacr.org/2004/246}
}