Efficient and Provably Secure Steganography

Ulrich Wölfel


Steganography is the art of encoding secret messages into unsuspicious covertexts, such that an adversary cannot distinguish the resulting stegotexts from original covertexts. A covertext consists of a sequence of documents. Whereas a large amount of work has gone into practical implementations of steganography, mostly for multimedia data as covertexts, only few theoretical analyses exist. In their seminal paper, Hopper et al. (2002b) presented black-box stegosystems, i.e., stegosystems that do not make any assumptions about the structure of covertexts, which can be proven secure. However, as these stegosystems only embed single bits per document, they are quite inefficient in terms of the transmission rate. An extension to multiple bits per document has been shown by Dedi´c et al. (2009) to be computationally infeasible. The aim of this thesis is to investigate how to achieve both security and efficiency (in the transmission rate) at the same time. First it is shown that so-called fixed-entropy samplers, which output low-min-entropy parts of documents, are hard to construct for even slightly structured channels. Due to this and Dedi´c et al’s result the black-box model of steganography appears to be a deadend. Therefore, a new model, called grey-box steganography, is suggested, in which the knowledge about the covertext channel is described by hypotheses, whose form depends on the structure of the channel. It is shown that efficient and secure steganography can be achieved for various hypothesis representations. Based on these results, future practical implementations of secure stegosystems appear possible. However, because the hypotheses have to be constructed by the steganographic encoder, e.g. by using algorithmic learning, there are limitations due to the hardness of learning certain concept classes. Starting with the observation that the commonly used notion of insecurity does not fit the situation in steganography, a new security notion, called detectability is proposed and three variants given. These are used in the analysis of two stegosystems that are both insecure, but achieve different results in terms of detectability. Detectability on average is determined to be best suited for security analyses in steganography. Furthermore, one of the analysed stegosystems, whose security depends on the difficulty of distinguishing between the output of two pseudorandom functions, presents a good candidate for future practical implementations, as it achieves both a good transmission rate and low detectability on average.
Gradverleihende Hochschule
Betreuer/-in / Berater/-in
  • Liskiewicz, Maciej, Betreuer*in
  • Krause, Matthias , Betreuer*in, Externe Person
PublikationsstatusVeröffentlicht - 2011


Untersuchen Sie die Forschungsthemen von „Efficient and Provably Secure Steganography“. Zusammen bilden sie einen einzigartigen Fingerprint.