Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-010 | 19th January 2015 11:23

Security Levels in Steganography -- Insecurity does not Imply Detectability


Authors: Maciej Li\'skiewicz, Rüdiger Reischuk, Ulrich Wölfel
Publication: 19th January 2015 11:25
Downloads: 2111


This paper takes a fresh look at security notions for steganography --
the art of encoding secret messages into unsuspicious covertexts
such that an adversary cannot distinguish the resulting stegotexts from original covertexts.
Stegosystems that fulfill the security notion used so far, however, are quite inefficient.
This setting is not able to quantify the power of the adversary and thus leads to extremely high
requirements. We will show that there exist stegosystems that are not secure with respect to
the measure considered so far, still cannot be detected by the adversary in practice.

This indicates that a different notion of security is needed which we call \emph{undetectability}.
We propose different variants of (un)-detectability and discuss their appropriateness.
By constructing concrete examples of stegosystems and covertext distributions
it is shown that among these measures only one manages to clearly and correctly
differentiate different levels of security when compared to an intuitive understanding
in real life situations. We have termed this \emph{detectability on average}.

As main technical contribution we design a framework for steganography
that exploits the difficulty to learn the covertext distribution.
This way, for the first time a tight analytical relationship between the task
of discovering the use of stegosystems and the task of differentiating between
possible covertext distributions is obtained.

ISSN 1433-8092 | Imprint