A One-Time Stegosystem and Applications to Efficient Covert Communication
Tóm tắt
We present the first information-theoretic steganographic protocol with an asymptotically optimal ratio of key length to message length that operates on arbitrary covertext distributions with constant min-entropy. Our results are also applicable to the computational setting: our stegosystem can be composed over a pseudorandom generator to send longer messages in a computationally secure fashion. In this respect our scheme offers a significant improvement in terms of the number of pseudorandom bits generated by the two parties in comparison to previous results known in the computational setting. Central to our approach for improving the overhead for general distributions is the use of combinatorial constructions that have been found to be useful in other contexts for derandomization: almost t-wise independent function families.
Tài liệu tham khảo
N. Alon, O. Goldreich, J. Håstad, R. Peralta, Simple construction of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289–304 (1992)
C. Cachin, An information-theoretic model for steganography. Inf. Comput. 192(1), 41–56 (2004)
G.D. Forney, Jr., Concatenated Codes. Research Monograph, vol. 37 (MIT Press, Cambridge 1966)
O. Goldreich, S. Goldwasser, S. Micali, How to construct random functions. J. ACM 33(4), 792–807 (1986)
N.J. Hopper, J. Langford, L. von Ahn, Provably secure steganography, in CRYPTO (2002), pp. 77–92
N.J. Hopper, L. von Ahn, J. Langford, Provably secure steganography. IEEE Trans. Comput. 58(5), 662–676 (2009)
A. Kiayias, Y. Raekow, A. Russell, Efficient steganography with provable security guarantees, in Information Hiding, ed. by M. Barni, J. Herrera-Joancomartí, S. Katzenbeisser, F. Pérez-González. Lecture Notes in Computer Science, vol. 3727 (Springer, Berlin, 2005), pp. 118–130. ISBN 3-540-29039-7
T. Mittelholzer, An information-theoretic approach to steganography and watermarking, in Information Hiding (1999), pp. 1–16
J. Naor, M. Naor, Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput. 22(4), 838–856 (1993)
M. Naor, O. Reingold, Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51(2), 231–262 (2004)
C.E. Shannon, A mathematical theory of communication. Bell Syst. Tech. J. 27, 379–423, July and October (1948), also see pp. 623–656
C.E. Shannon, W. Weaver, The Mathematical Theory of Communication (University of Illinois Press, Urbana, 1949)
G.J. Simmons, The prisoners’ problem and the subliminal channel, in CRYPTO (1983), pp. 51–67
L. von Ahn, N.J. Hopper, Public-key steganography, in Advances in Cryptology—Proceedings of Eurocrypt ’04 (Springer, Berlin, 2004), pp. 323–341
J. Zöllner, H. Federrath, H. Klimant, A. Pfitzmann, R. Piotraschke, A. Westfeld, G. Wicke, G. Wolf, Modeling the security of steganographic systems, in Information Hiding (1998), pp. 344–354