On the Gold Standard for Security of Universal Steganography


While symmetric-key steganography is quite well understood both in the information-theoretic and in the computational setting, many fundamental questions about its public-key counterpart resist persistent attempts to solve them. The computational model for public-key steganography was proposed by von Ahn and Hopper in EUROCRYPT 2004. At TCC 2005, Backes and Cachin gave the first universal public-key stegosystem – i.e. one that works on all channels – achieving security against replayable chosen-covertext attacks (ss-rcca) and asked whether security against non-replayable chosen-covertext attacks (ss-cca) is achievable. Later, Hopper (ICALP 2005) provided such a stegosystem for every efficiently sampleable channel, but did not achieve universality. He posed the question whether universality and ss-cca-security can be achieved simultaneously. No progress on this question has been achieved since more than a decade. In our work we solve Hopper’s problem in a somehow complete manner: As our main positive result we design an ss-cca-secure stegosystem that works for every memoryless channel. On the other hand, we prove that this result is the best possible in the context of universal steganography. We provide a family of 0-memoryless channels – where the already sent documents have only marginal influence on the current distribution – and prove that no ss-cca-secure steganography for this family exists in the standard non-look-ahead model.
Original languageEnglish
Title of host publicationEUROCRYPT 2018: Advances in Cryptology – EUROCRYPT 2018
EditorsJesper Buus Nielsen, Vincent Rijmen
Number of pages32
Volume10820 LNCS
PublisherSpringer Berlin Heidelberg
Publication date2018
ISBN (Print)978-3-319-78380-2
ISBN (Electronic)978-3-319-78381-9
Publication statusPublished - 2018
Event37th Annual International Conference on the Theory and Applications of Cryptographic Techniques - Tel Aviv, Israel
Duration: 29.04.201803.05.2018
Conference number: 212999


Dive into the research topics of 'On the Gold Standard for Security of Universal Steganography'. Together they form a unique fingerprint.

Cite this