Abstract
Recent work on theoretical aspects of steganography resulted in the construction of oracle-based stegosystems. It has been shown that these can be made secure against the steganography equivalents of common cryptographic attacks. In this paper we use methods from complexity theory to investigate the efficiency of sampling from practically relevant types of channels. We show that there are channels that cannot be efficiently used in oracle-based stegosystems. By classifying channels based on their usability for stegosystems, we provide a means to select suitable channels for their practical implementation.
Supported by DFG research grant RE 672/5-1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Hopper, N.J., Langford, J., von Ahn, L.: Provably secure steganography. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 77–92. Springer, Heidelberg (2002)
Anderson, R.J., Petitcolas, F.A.P.: On the limits of steganography. IEEE Journal of Selected Areas of Communications 16(4), 474–481 (1998)
von Ahn, L., Hopper, N.J.: Public-key steganography. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 323–341. Springer, Heidelberg (2004)
Le, T.V., Kurosawa, K.: Efficient public key steganography secure against adaptively chosen stegotext attacks. Technical Report 2003/244, IACR Archive (2003)
Backes, M., Cachin, C.: Public-key steganography with active attacks. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 210–226. Springer, Heidelberg (2005)
Lysyanskaya, A., Meyerovich, M.: Provably secure steganography with imperfect sampling. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol. 3958, pp. 123–139. Springer, Heidelberg (2006)
Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W.H. Freeman & Co., New York (1979)
Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (2000)
Iwama, K., Tamaki, S.: Improved upper bounds for 3-sat. In: Proc. ACM-SIAM Symposium on Discrete algorithms - ACM 2004, pp. 328–328. SIAM, Philadelphia (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hundt, C., Liśkiewicz, M., Wölfel, U. (2006). Provably Secure Steganography and the Complexity of Sampling. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_75
Download citation
DOI: https://doi.org/10.1007/11940128_75
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)