Hard Communication Channels for Steganography


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.

Original languageEnglish
Title of host publication27th International Symposium on Algorithms and Computation (ISAAC 2016)
EditorsSeok-Hee Hong
Number of pages16
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Publication date02.12.2016
ISBN (Print)978-3-95977-026-2
Publication statusPublished - 02.12.2016
Event27th International Symposium on Algorithms and Computation (ISAAC 2016)
- Darling Harbour, Sydney, Australia
Duration: 12.12.201614.12.2016


Dive into the research topics of 'Hard Communication Channels for Steganography'. Together they form a unique fingerprint.

Cite this