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.