• Previous Article
    List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes
  • AMC Home
  • This Issue
  • Next Article
    Characterization and constructions of self-dual codes over $\mathbb Z_2\times \mathbb Z_4$
August  2012, 6(3): 273-285. doi: 10.3934/amc.2012.6.273

Wet paper codes and the dual distance in steganography

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

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.
Citation: Carlos Munuera, Morgan Barbier. Wet paper codes and the dual distance in steganography. Advances in Mathematics of Communications, 2012, 6 (3) : 273-285. doi: 10.3934/amc.2012.6.273
References:
[1]

D. Augot, M. Barbier and C. Fontaine, Ensuring message embedding in wet paper steganography,, in, (2011), 244.

[2]

J. Brierbrauer and J. Fridrich, Constructing good covering codes for applications in steganography,, in, (2008), 1. 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. doi: 10.1007/s11424-008-9103-0.

[4]

C. Cooper, On the rank of random matrices,, Random Struc. Algor., 16 (2000), 209. doi: 10.1002/(SICI)1098-2418(200003)16:2<209::AID-RSA6>3.0.CO;2-1.

[5]

R. Crandall, Some notes on steganography,, \url{http://os.inf.tu-dresden.de/ westfeld}, ().

[6]

C. Fontaine and F. Galand, How Reed-Solomon codes can improve steganographic schemes,, in, (2007), 130.

[7]

J. Fridrich, M. Goljan, P. Lisonek and D. Soukal, Writing on wet paper,, IEEE Trans. Signal Proc., 53 (2005), 3923. doi: 10.1109/TSP.2005.855393.

[8]

J. Fridrich, M. Goljan and D. Soukal, Efficient wet paper codes,, in, (2005). doi: 10.1007/b104759.

[9]

J. Fridrich, M. Goljan and D. Soukal, Steganography via codes for memory with defective cells,, in, (2005), 1521.

[10]

J. Fridrich, M. Goljan and D. Soukal, Wet paper codes with improved embedding efficiency,, IEEE Trans. Inform. Forens. Secur., 1 (2006), 102. doi: 10.1109/TIFS.2005.863487.

[11]

B. J. Hamilton, SINCGARS system improvement program (SIP) specific radio improvement,, in, (1996), 397.

[12]

R. W. Hamming, "The Art of Probability for Scientists and Engineers,'', Westview Press, (1994).

[13]

A. S. Hedayat, N. J. A. Sloane and J. Stufken, "Orthogonal Arrays: Theory and Applications,'', Springer-Verlag, (1999).

[14]

M. Keinänen, "Techniques for Solving Boolean Equation Systems,'', Ph.D thesis, (2006).

[15]

V. F. Kolchin, "Random Graphs,'', Cambridge University Press, (1999).

[16]

F. J. MacWilliams and N. J. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland Publishing Co., (1977).

[17]

MinT, Online database for optimal parameters of $(t, m, s)$-nets, $(t, s)$-sequences, orthogonal arrays, linear codes, and OOAs,, available at \url{http://mint.sbg.ac.at/}, ().

[18]

C. Munuera, On the generalized Hamming weights of geometric Goppa codes,, IEEE Trans. Inform. Theory, 40 (1994), 2092. doi: 10.1109/18.340488.

[19]

M. Nadler, A 32-point $n=12$, $d=5$ code,, IRE Trans. Inform. Theory, 8 (1962). doi: 10.1109/TIT.1962.1057670.

[20]

D. Schönfeld and A. Winkler, Embedding with syndrome coding based on BCH codes,, in, (2006), 214.

[21]

D. Schönfeld and A. Winkler, Reducing the complexity of syndrome coding for embedding,, in, (2007), 145.

[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. doi: 10.1109/18.179365.

[23]

D. Stinson, Resilient functions and large sets of orthogonal arrays,, Congressus Numerantium, 92 (1993), 105.

[24]

C. Studholme and I. F. Blake, Random matrices and codes for the erasure channel,, Algoritmica, 56 (2010), 605. 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. doi: 10.1109/TIT.1972.1054904.

[26]

J. H. van Lint, "Introduction to Coding Theory,'', Springer-Verlag, (1982).

[27]

V. K. Wei, Generalized Hamming weights for linear codes,, IEEE Trans. Inform. Theory, 37 (1991), 1412. 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, (2008), 60.

show all references

References:
[1]

D. Augot, M. Barbier and C. Fontaine, Ensuring message embedding in wet paper steganography,, in, (2011), 244.

[2]

J. Brierbrauer and J. Fridrich, Constructing good covering codes for applications in steganography,, in, (2008), 1. 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. doi: 10.1007/s11424-008-9103-0.

[4]

C. Cooper, On the rank of random matrices,, Random Struc. Algor., 16 (2000), 209. doi: 10.1002/(SICI)1098-2418(200003)16:2<209::AID-RSA6>3.0.CO;2-1.

[5]

R. Crandall, Some notes on steganography,, \url{http://os.inf.tu-dresden.de/ westfeld}, ().

[6]

C. Fontaine and F. Galand, How Reed-Solomon codes can improve steganographic schemes,, in, (2007), 130.

[7]

J. Fridrich, M. Goljan, P. Lisonek and D. Soukal, Writing on wet paper,, IEEE Trans. Signal Proc., 53 (2005), 3923. doi: 10.1109/TSP.2005.855393.

[8]

J. Fridrich, M. Goljan and D. Soukal, Efficient wet paper codes,, in, (2005). doi: 10.1007/b104759.

[9]

J. Fridrich, M. Goljan and D. Soukal, Steganography via codes for memory with defective cells,, in, (2005), 1521.

[10]

J. Fridrich, M. Goljan and D. Soukal, Wet paper codes with improved embedding efficiency,, IEEE Trans. Inform. Forens. Secur., 1 (2006), 102. doi: 10.1109/TIFS.2005.863487.

[11]

B. J. Hamilton, SINCGARS system improvement program (SIP) specific radio improvement,, in, (1996), 397.

[12]

R. W. Hamming, "The Art of Probability for Scientists and Engineers,'', Westview Press, (1994).

[13]

A. S. Hedayat, N. J. A. Sloane and J. Stufken, "Orthogonal Arrays: Theory and Applications,'', Springer-Verlag, (1999).

[14]

M. Keinänen, "Techniques for Solving Boolean Equation Systems,'', Ph.D thesis, (2006).

[15]

V. F. Kolchin, "Random Graphs,'', Cambridge University Press, (1999).

[16]

F. J. MacWilliams and N. J. Sloane, "The Theory of Error-Correcting Codes,'', North-Holland Publishing Co., (1977).

[17]

MinT, Online database for optimal parameters of $(t, m, s)$-nets, $(t, s)$-sequences, orthogonal arrays, linear codes, and OOAs,, available at \url{http://mint.sbg.ac.at/}, ().

[18]

C. Munuera, On the generalized Hamming weights of geometric Goppa codes,, IEEE Trans. Inform. Theory, 40 (1994), 2092. doi: 10.1109/18.340488.

[19]

M. Nadler, A 32-point $n=12$, $d=5$ code,, IRE Trans. Inform. Theory, 8 (1962). doi: 10.1109/TIT.1962.1057670.

[20]

D. Schönfeld and A. Winkler, Embedding with syndrome coding based on BCH codes,, in, (2006), 214.

[21]

D. Schönfeld and A. Winkler, Reducing the complexity of syndrome coding for embedding,, in, (2007), 145.

[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. doi: 10.1109/18.179365.

[23]

D. Stinson, Resilient functions and large sets of orthogonal arrays,, Congressus Numerantium, 92 (1993), 105.

[24]

C. Studholme and I. F. Blake, Random matrices and codes for the erasure channel,, Algoritmica, 56 (2010), 605. 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. doi: 10.1109/TIT.1972.1054904.

[26]

J. H. van Lint, "Introduction to Coding Theory,'', Springer-Verlag, (1982).

[27]

V. K. Wei, Generalized Hamming weights for linear codes,, IEEE Trans. Inform. Theory, 37 (1991), 1412. 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, (2008), 60.

[1]

Andrew Klapper, Andrew Mertz. The two covering radius of the two error correcting BCH code. Advances in Mathematics of Communications, 2009, 3 (1) : 83-95. doi: 10.3934/amc.2009.3.83

[2]

Selim Esedoḡlu, Fadil Santosa. Error estimates for a bar code reconstruction method. Discrete & Continuous Dynamical Systems - B, 2012, 17 (6) : 1889-1902. doi: 10.3934/dcdsb.2012.17.1889

[3]

José Gómez-Torrecillas, F. J. Lobillo, Gabriel Navarro. Information--bit error rate and false positives in an MDS code. Advances in Mathematics of Communications, 2015, 9 (2) : 149-168. doi: 10.3934/amc.2015.9.149

[4]

Masaaki Harada, Takuji Nishimura. An extremal singly even self-dual code of length 88. Advances in Mathematics of Communications, 2007, 1 (2) : 261-267. doi: 10.3934/amc.2007.1.261

[5]

Michael Kiermaier, Johannes Zwanzger. A $\mathbb Z$4-linear code of high minimum Lee distance derived from a hyperoval. Advances in Mathematics of Communications, 2011, 5 (2) : 275-286. doi: 10.3934/amc.2011.5.275

[6]

Laura Luzzi, Ghaya Rekaya-Ben Othman, Jean-Claude Belfiore. Algebraic reduction for the Golden Code. Advances in Mathematics of Communications, 2012, 6 (1) : 1-26. doi: 10.3934/amc.2012.6.1

[7]

Irene Márquez-Corbella, Edgar Martínez-Moro, Emilio Suárez-Canedo. On the ideal associated to a linear code. Advances in Mathematics of Communications, 2016, 10 (2) : 229-254. doi: 10.3934/amc.2016003

[8]

Serhii Dyshko. On extendability of additive code isometries. Advances in Mathematics of Communications, 2016, 10 (1) : 45-52. doi: 10.3934/amc.2016.10.45

[9]

M. De Boeck, P. Vandendriessche. On the dual code of points and generators on the Hermitian variety $\mathcal{H}(2n+1,q^{2})$. Advances in Mathematics of Communications, 2014, 8 (3) : 281-296. doi: 10.3934/amc.2014.8.281

[10]

Sihuang Hu, Gabriele Nebe. There is no $[24,12,9]$ doubly-even self-dual code over $\mathbb F_4$. Advances in Mathematics of Communications, 2016, 10 (3) : 583-588. doi: 10.3934/amc.2016027

[11]

Masaaki Harada, Ethan Novak, Vladimir D. Tonchev. The weight distribution of the self-dual $[128,64]$ polarity design code. Advances in Mathematics of Communications, 2016, 10 (3) : 643-648. doi: 10.3934/amc.2016032

[12]

Olof Heden. The partial order of perfect codes associated to a perfect code. Advances in Mathematics of Communications, 2007, 1 (4) : 399-412. doi: 10.3934/amc.2007.1.399

[13]

Martino Borello, Francesca Dalla Volta, Gabriele Nebe. The automorphism group of a self-dual $[72,36,16]$ code does not contain $\mathcal S_3$, $\mathcal A_4$ or $D_8$. Advances in Mathematics of Communications, 2013, 7 (4) : 503-510. doi: 10.3934/amc.2013.7.503

[14]

M. Delgado Pineda, E. A. Galperin, P. Jiménez Guerra. MAPLE code of the cubic algorithm for multiobjective optimization with box constraints. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 407-424. doi: 10.3934/naco.2013.3.407

[15]

Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015

[16]

Anna-Lena Horlemann-Trautmann, Kyle Marshall. New criteria for MRD and Gabidulin codes and some Rank-Metric code constructions. Advances in Mathematics of Communications, 2017, 11 (3) : 533-548. doi: 10.3934/amc.2017042

[17]

Denis S. Krotov, Patric R. J.  Östergård, Olli Pottonen. Non-existence of a ternary constant weight $(16,5,15;2048)$ diameter perfect code. Advances in Mathematics of Communications, 2016, 10 (2) : 393-399. doi: 10.3934/amc.2016013

[18]

Jianying Fang. 5-SEEDs from the lifted Golay code of length 24 over Z4. Advances in Mathematics of Communications, 2017, 11 (1) : 259-266. doi: 10.3934/amc.2017017

[19]

Bram van Asch, Frans Martens. A note on the minimum Lee distance of certain self-dual modular codes. Advances in Mathematics of Communications, 2012, 6 (1) : 65-68. doi: 10.3934/amc.2012.6.65

[20]

Daniel Heinlein, Michael Kiermaier, Sascha Kurz, Alfred Wassermann. A subspace code of size $ \bf{333} $ in the setting of a binary $ \bf{q} $-analog of the Fano plane. Advances in Mathematics of Communications, 2019, 13 (3) : 457-475. doi: 10.3934/amc.2019029

2017 Impact Factor: 0.564

Metrics

  • PDF downloads (3)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]