Document Open Access Logo

Hard Communication Channels for Steganography

Authors Sebastian Berndt, Maciej Liskiewicz

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2016.16.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

Sebastian Berndt
Maciej Liskiewicz

Cite AsGet BibTex

Sebastian Berndt and Maciej Liskiewicz. Hard Communication Channels for Steganography. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ISAAC.2016.16

Abstract

This paper considers steganography - the concept of hiding the presence of secret messages in legal communications - in the computational setting and its relation to cryptography. Very recently the first (non-polynomial time) steganographic protocol has been shown which, for any communication channel, is provably secure, reliable, and has nearly optimal bandwidth. The security is unconditional, i.e. it does not rely on any unproven complexity-theoretic assumption. This disproves the claim that the existence of one-way functions and access to a communication channel oracle are both necessary and sufficient conditions for the existence of secure steganography in the sense that secure and reliable steganography exists independently of the existence of one-way functions. In this paper, we prove that this equivalence also does not hold in the more realistic setting, where the stegosystem is polynomial time bounded. We prove this by constructing (a) a channel for which secure steganography exists if and only if one-way functions exist and (b) another channel such that secure steganography implies that no one-way functions exist. We therefore show that security-preserving reductions between cryptography and steganography need to be treated very carefully.
Keywords
  • provable secure steganography
  • cryptographic assumptions
  • pseudoran- dom functions
  • one-way functions
  • signature schemes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Sanjeev Arora and Boaz Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  2. Michael Backes and Christian Cachin. Public-key steganography with active attacks. In Theory of Cryptography Conference (TCC), pages 210-226. Springer, 2005. Google Scholar
  3. Mihir Bellare, Anand Desai, Eron Jokipii, and Phillip Rogaway. A concrete security treatment of symmetric encryption. In Foundations of Computer Science (FOCS), pages 394-403. IEEE, 1997. Google Scholar
  4. Sebastian Berndt and Maciej Liśkiewicz. Provable secure universal steganography of optimal rate. In Information Hiding and Multimedia Security (IH&MMSec). ACM, 2016. Google Scholar
  5. Christian Cachin. An information-theoretic model for steganography. Information and Computation, 192(1):41-56, 2004. URL: http://dx.doi.org/10.1016/j.ic.2004.02.003.
  6. Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, and Amit Sahai. Covert multi-party computation. In Foundations of Computer Science (FOCS), pages 238-248. IEEE, 2007. Google Scholar
  7. Chongwon Cho, Dana Dachman-Soled, and Stanisław Jarecki. Efficient concurrent covert computation of string equality and set intersection. In Topics in Cryptology-CT-RSA, pages 164-179. Springer, 2016. Google Scholar
  8. Pedro Comesaña and Fernando Pérez-González. On the capacity of stegosystems. In Multimedia &Security (MMSec), pages 15-24. ACM, 2007. Google Scholar
  9. Anindya De, Ilias Diakonikolas, and Rocco A. Servedio. Learning from satisfying assignments. In Symp. on Discrete Algorithms (SODA), pages 478-497. ACM-SIAM, 2015. Google Scholar
  10. Nenad Dedić, Gene Itkis, Leonid Reyzin, and Scott Russell. Upper and lower bounds on black-box steganography. Journal of Cryptology, 22(3):365-394, 2009. Google Scholar
  11. Cynthia Dwork. Differential privacy. In Automata, Languages and Programming (ICALP), pages 1-12. Springer, 2006. Google Scholar
  12. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil P. Vadhan. On the complexity of differentially private data release: efficient algorithms and hardness results. In Symp. on Theory of Computing (STOC), pages 381-390, 2009. Google Scholar
  13. Shimon Even, Oded Goldreich, and Silvio Micali. On-line/off-line digital signatures. Journal of Cryptology, 9(1):35-67, 1996. Google Scholar
  14. Nelly Fazio, Antonio R Nicolosi, and Irippuge Milinda Perera. Broadcast steganography. In Topics in Cryptology-CT-RSA 2014, pages 64-84. Springer, 2014. Google Scholar
  15. Tomás Filler, Andrew D. Ker, and Jessica J. Fridrich. The square root law of steganographic capacity for markov covers. In Media Forensics and Security I, part of the IS&T-SPIE Electronic Imaging Symposium, page 725408, 2009. Google Scholar
  16. Jessica Fridrich. Steganography in digital media: principles, algorithms, and applications. Cambridge University Press, 2009. Google Scholar
  17. Oded Goldreich, Shafi Goldwasser, and Silvio Micali. How to construct random functions. Journal of the ACM (JACM), 33(4):792-807, 1986. Google Scholar
  18. Vipul Goyal and Abhishek Jain. On the round complexity of covert computation. In Symp. on Theory of Computing (STOC), pages 191-200. ACM, 2010. Google Scholar
  19. Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-1396, 1999. Google Scholar
  20. Nicholas Hopper. On steganographic chosen covertext security. In Automata, Languages and Programming (ICALP), volume 3580, pages 311-323. Springer, 2005. Google Scholar
  21. Nicholas J Hopper. Toward a theory of steganography. Technical report, Technical Report CMU-CS-04-157, Carnegie Mellon Univ., 2004. Google Scholar
  22. Nicholas J. Hopper, John Langford, and Luis von Ahn. Provably secure steganography. In Advances in Cryptology (CRYPTO), pages 77-92. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45708-9_6.
  23. Nicholas J. Hopper, Luis von Ahn, and John Langford. Provably secure steganography. Computers, IEEE Transactions on, 58(5):662-676, 2009. Google Scholar
  24. Sune K Jakobsen and Claudio Orlandi. How to bootstrap anonymous communication. In Conf. on Innovations in Theoretical Computer Science (ITCS), pages 333-344. ACM, 2016. Google Scholar
  25. Stefan Katzenbeisser and Fabien A.P. Petitcolas. Defining security in steganographic systems. In Electronic Imaging 2002, pages 50-56. SPIE, 2002. Google Scholar
  26. Andrew D. Ker, Patrick Bas, Rainer Böhme, Rémi Cogranne, Scott Craver, Tomáš Filler, Jessica Fridrich, and Tomáš Pevnỳ. Moving steganography and steganalysis from the laboratory into the real world. In Information Hiding and Multimedia Security (IH&MMSec), pages 45-58. ACM, 2013. Google Scholar
  27. Andrew D. Ker, Tomás Pevný, Jan Kodovský, and Jessica J. Fridrich. The square root law of steganographic capacity. In Multimedia Security (MMSec), pages 107-116. ACM, 2008. Google Scholar
  28. Aggelos Kiayias, Alexander Russell, and Narasimha Shashidhar. Key-efficient steganography. In Information Hiding (IH), pages 142-159. Springer, 2012. Google Scholar
  29. Tri Van Le and Kaoru Kurosawa. Bandwidth optimal steganography secure against adaptive chosen stegotext attacks. In Information Hiding (IH), pages 297-313. Springer, 2006. Google Scholar
  30. Leonid A. Levin. One way functions and pseudorandom generators. Combinatorica, 7(4):357-363, 1987. Google Scholar
  31. Maciej Liśkiewicz, Rüdiger Reischuk, and Ulrich Wölfel. Security levels in steganography - insecurity does not imply detectability. Electronic Colloquium on Computational Complexity (ECCC), 22(10), 2015. Google Scholar
  32. Michael Luby and Charles Rackoff. How to construct pseudorandom permutations from pseudorandom functions. SIAM Journal on Computing, 17(2):373-386, 1988. Google Scholar
  33. Boris Ryabko and Daniil Ryabko. Constructing perfect steganographic systems. Information and Computation, 209(9):1223-1230, 2011. Google Scholar
  34. Jonathan Ullman. Answering n^2+o(1) counting queries with differential privacy is hard. In Symp. on Theory of Computing (STOC), pages 361-370. ACM, 2013. Google Scholar
  35. Luis von Ahn, Nicholas Hopper, and John Langford. Covert two-party computation. In Symposium on Theory of Computing (STOC), pages 513-522. ACM, 2005. Google Scholar
  36. Luis von Ahn and Nicholas J Hopper. Public-key steganography. In Advances in Cryptology (EUROCRYPT), pages 323-341. Springer, 2004. Google Scholar
  37. Ying Wang and Pierre Moulin. Perfectly secure steganography: Capacity, error exponents, and code constructions. Information Theory, IEEE Transactions on, 54(6):2706-2722, 2008. Google Scholar
  38. Elżbieta Zielińska, Wojciech Mazurczyk, and Krzysztof Szczypiorski. Trends in steganography. Communications of the ACM, 57(3):86-95, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact