### On the Gold Standard for Security of Universal Steganography

Sebastian Berndt and Maciej Liśkiewicz

##### Abstract

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.

Available format(s)
Category
Foundations
Publication info
A minor revision of an IACR publication in EUROCRYPT 2018
Keywords
Eurocrypt 2018steganographypublic-key cryptography
Contact author(s)
sebastian berndt @ gmail com
History
Short URL
https://ia.cr/2018/106

CC BY

BibTeX

@misc{cryptoeprint:2018/106,
author = {Sebastian Berndt and Maciej Liśkiewicz},
title = {On the Gold Standard for Security of Universal Steganography},
howpublished = {Cryptology ePrint Archive, Paper 2018/106},
year = {2018},
note = {\url{https://eprint.iacr.org/2018/106}},
url = {https://eprint.iacr.org/2018/106}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.