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.