Wet paper codes and the dual distance in steganography

Carlos Munuera; Morgan Barbier

doi:10.3934/amc.2012.6.273

Article Contents

2012, Volume 6, Issue 3: 273-285. Doi: 10.3934/amc.2012.6.273

This issue Previous Article List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes Next Article Characterization and constructions of self-dual codes over $\mathbb Z_2\times \mathbb Z_4$

Wet paper codes and the dual distance in steganography

Carlos Munuera^1, and
Morgan Barbier^2,

1.
Department of Applied Mathematics, University of Valladolid, Avda Salamanca SN, 47014 Valladolid, Castilla
2.
Computer Science Laboratory, École Polytechnique, 91 128 Palaiseau CEDEX, INRIA Saclay, ÎIle de France

Received: March 2011

Revised: January 2012

Published: August 2012

Abstract / Introduction Related Papers Cited by

Abstract

In 1998 Crandall introduced a method based on coding theory to secretly embed a message in a digital support such as an image. Later, in 2005, Fridrich et al. improved this method to minimize the distortion introduced by the embedding; a process called wet paper. However, as previously emphasized in the literature, this method can fail during the embedding step. Here we find sufficient and necessary conditions to guarantee a successful embedding, by studying the dual distance of a linear code. Since these results are essentially of combinatorial nature, they can be generalized to systematic codes, a large family containing all linear codes. We also compute the exact number of embedding solutions and point out the relationship between wet paper codes and orthogonal arrays.

Keywords:

Mathematics Subject Classification: Primary: 94A60; Secondary: 94B60.

Citation:

Related Papers

Cited by

References

[1]	D. Augot, M. Barbier and C. Fontaine, Ensuring message embedding in wet paper steganography, in "Transactions on Thirteenth IMA International Conference on Cryptography and Coding,'' Springer-Verlag, Berlin, Heidelberg, (2011), 244-258.
[2]	J. Brierbrauer and J. Fridrich, Constructing good covering codes for applications in steganography, in "Transactions on Data Hiding and Multimedia Security III,'' Springer-Verlag, (2008), 1-22.doi: 10.1007/978-3-540-69019-1_1.
[3]	F. Chai, X. S. Gao and C. Yuan, A characteristic set method for solving Boolean equations and applications in cryptanalysis of stream ciphers, J. Sys. Sci. Compl., 21 (2008), 191-208.doi: 10.1007/s11424-008-9103-0.
[4]	C. Cooper, On the rank of random matrices, Random Struc. Algor., 16 (2000), 209-232.doi: 10.1002/(SICI)1098-2418(200003)16:2<209::AID-RSA6>3.0.CO;2-1.
[5]	R. Crandall, Some notes on steganography, http://os.inf.tu-dresden.de/ westfeld
[6]	C. Fontaine and F. Galand, How Reed-Solomon codes can improve steganographic schemes, in "Information Hiding 9th International Workshop,'' Springer-Verlag, (2007), 130-144.
[7]	J. Fridrich, M. Goljan, P. Lisonek and D. Soukal, Writing on wet paper, IEEE Trans. Signal Proc., 53 (2005), 3923-3935.doi: 10.1109/TSP.2005.855393.
[8]	J. Fridrich, M. Goljan and D. Soukal, Efficient wet paper codes, in "Proceedings of Information Hiding,'' Springer-Verlag, 2005.doi: 10.1007/b104759.
[9]	J. Fridrich, M. Goljan and D. Soukal, Steganography via codes for memory with defective cells, in "Proceedings of the Forty-Third Annual Allerton Conference On Communication, Control and Computing,'' (2005), 1521-1538.
[10]	J. Fridrich, M. Goljan and D. Soukal, Wet paper codes with improved embedding efficiency, IEEE Trans. Inform. Forens. Secur., 1 (2006), 102-110.doi: 10.1109/TIFS.2005.863487.
[11]	B. J. Hamilton, SINCGARS system improvement program (SIP) specific radio improvement, in "Proceedings of 1996 Tactical Communications Conference,'' (1996), 397-406.
[12]	R. W. Hamming, "The Art of Probability for Scientists and Engineers,'' Westview Press, New York, 1994.
[13]	A. S. Hedayat, N. J. A. Sloane and J. Stufken, "Orthogonal Arrays: Theory and Applications,'' Springer-Verlag, New York, 1999.
[14]	M. Keinänen, "Techniques for Solving Boolean Equation Systems,'' Ph.D thesis, Espoo, Finland, 2006.
[15]	V. F. Kolchin, "Random Graphs,'' Cambridge University Press, Cambridge, 1999.
[16]	F. J. MacWilliams and N. J. Sloane, "The Theory of Error-Correcting Codes,'' North-Holland Publishing Co., Amsterdam, 1977.
[17]	MinT, Online database for optimal parameters of $(t, m, s)$-nets, $(t, s)$-sequences, orthogonal arrays, linear codes, and OOAs, available at http://mint.sbg.ac.at/
[18]	C. Munuera, On the generalized Hamming weights of geometric Goppa codes, IEEE Trans. Inform. Theory, 40 (1994), 2092-2099.doi: 10.1109/18.340488.
[19]	M. Nadler, A 32-point $n=12$, $d=5$ code, IRE Trans. Inform. Theory, 8 (1962), 58.doi: 10.1109/TIT.1962.1057670.
[20]	D. Schönfeld and A. Winkler, Embedding with syndrome coding based on BCH codes, in "Proceedings 8th ACM Workshop on Multimedia and Security,'' (2006), 214-223.
[21]	D. Schönfeld and A. Winkler, Reducing the complexity of syndrome coding for embedding, in "Proceedings 10th ACM Workshop on Information Hiding,'' Springer-Verlag, (2007), 145-158.
[22]	B.-Z. Shen, A Justesen construction of binary concatenated codes that asymptotically meet the Zyablov bound for low rate, IEEE Trans. Inform. Theory, 39 (1993), 239-242.doi: 10.1109/18.179365.
[23]	D. Stinson, Resilient functions and large sets of orthogonal arrays, Congressus Numerantium, 92 (1993), 105-110.
[24]	C. Studholme and I. F. Blake, Random matrices and codes for the erasure channel, Algoritmica, 56 (2010), 605-620.doi: 10.1007/s00453-008-9192-0.
[25]	J. H. van Lint, A new description of the Nadler code, IEEE Trans. Inform. Theory, 18 (1972), 825-826.doi: 10.1109/TIT.1972.1054904.
[26]	J. H. van Lint, "Introduction to Coding Theory,'' Springer-Verlag, New York, 1982.
[27]	V. K. Wei, Generalized Hamming weights for linear codes, IEEE Trans. Inform. Theory, 37 (1991), 1412-1418.doi: 10.1109/18.133259.
[28]	W. Zhang, X. Zhang and S. Wang, Maximizing embedding efficiency by combining Hamming codes and wet paper codes, in "Proceedings 10th International Workshop on Information Hiding,'' Springer-Verlag, (2008), 60-71.