Minimizing the embedding impact in steganography

ABSTRACT

In this paper, we study the trade-off in steganography between the number of embedding changes and their amplitude. We assume that each element of the cover image is assigned a scalar value that measures the impact of making an embedding change at that pixel (e.g., the embedding distortion). Given the embedding impact profile of all pixels, we derive an analytic formula for the optimal number of pixels that should be used in combination with syndrome coding to minimize the overall embedding impact. We interpret the results and formulate several "rules of thumb" that should improve steganographic security. Contrary to what has been recommended in the literature before, our analysis implies that it is never optimal to only use the pixels with the smallest embedding impact. We also study q-ary embedding in the spatial domain and conclude that the smallest embedding impact is achieved for ternary schemes. This confirms some empirically derived facts previously published elsewhere.

REFERENCES

• 1: G.J. Simmons, "The Prisoners' Problem and the Subliminal Channel," CRYPTO83 -- Advances in Cryptology, August 22-24, pp. 51--67, 1984.
• 2: Stefan Katzenbeisser , Fabien A. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech House, Inc., Norwood, MA, 2000
• 3: R.J. Anderson and F.A.P. Petitcolas, "On the Limits of Steganography", IEEE Journal of Selected Areas in Communications, Special Issue on Copyright and Privacy Protection, vol. 16(4), pp. 474--481, 1998.
• 4: Christian Cachin, An Information-Theoretic Model for Steganography, Proceedings of the Second International Workshop on Information Hiding, p.306-318, April 14-17, 1998
• 5: Jan Zöllner , Hannes Federrath , Herbert Klimant , Andreas Pfitzmann , Rudi Piotraschke , Andreas Westfeld , Guntram Wicke , Gritta Wolf, Modeling the Security of Steganographic Systems, Proceedings of the Second International Workshop on Information Hiding, p.344-354, April 14-17, 1998
• 6: P. Sallee, "Model Based Steganography", in T. Kalker, I.J. Cox, Yong Man Ro (editors), International Workshop on Digital Watermarking, Lecture Notes in Computer Science, vol. 2939, Springer-Verlag, New York, pp. 154--167, 2004.
• 7: S. Katzenbeisser and F.A.P. Petitcolas, "Defining Security in Steganographic Systems", Proc. SPIE, Electronic Imaging, Security and Watermarking of Multimedia Contents IV, vol. 4675, Electronic Imaging 2000, San Jose, CA, pp. 50--56, 2002.
• 8: J. Fridrich, M. Goljan, and D. Soukal, "Perturbed Quantization Steganography", ACM Multimedia and Security Journal, vol. 11(2), pp. 98--107, 2005.
• 9: J. Fridrich, M. Goljan, and D. Soukal, "Wet paper Codes with Improved Embedding Efficiency," IEEE Transactions on Information Security and Forensics, vol. 1(1), pp. 102--110, March 2006.
• 10: Y. Kim, Z. Duric, and D. Richards, "Modified Matrix Encoding Technique for Minimal Distortion Steganography," to appear in Proc. 8th Information Hiding Workshop, July 10-12, Washington, DC, 2006.
• 11: Andreas Westfeld, F5-A Steganographic Algorithm, Proceedings of the 4th International Workshop on Information Hiding, p.289-302, April 25-27, 2001
• 12: R. Crandall, "Some Notes on Steganography", posted on Steganography Mailing List, http://os.inf.tu-dresden.de/~westfeld/crandall.pdf, 1998.
• 13: F. Galand and G. Kabatiansky, "Information Hiding by Coverings," in Proc. ITW2003, pp. 151--154, (Paris, France), 2003.
• 14: J. Fridrich, P. Lisoněk, and D. Soukal, "On Embedding Efficiency," to appear in Proc. 8th Information Hiding Workshop, Washington, DC, July 10-12, 2006.
• 15: G. D. Cohen, I. Honkala, S. Litsyn, and A. Lobstein, Covering Codes, vol. 54, Elsevier, North-Holland Mathematical Library, 1997.
• 16: M. J. Wainwright E. and Maneva, "Lossy Source Encoding via Message-Passing and Decimation over Generalized Codewords of LDGM Codes," in Proceedings of the International Symposium on Information Theory, Adelaide, Australia, 2005.
• 17: M. van Dijk and F. M. J. Willems, "Embedding Information in Grayscale Images," in Proc. of the 22nd Symposium on Information and Communication Theory in the Benelux, Enschede, The Netherlands, May 15-16, pp. 147--154, 2001.
• 18: D. Soukal, J. Fridrich, and M. Goljan, "Maximum Likelihood Estimation of Secret Message Length Embedded using PMK Steganography in Spatial Domain," in Proc. SPIE, Electronic Imaging, Security, Steganography, and Watermarking of Multimedia Contents VII, vol. 5681, San Jose, CA, January 16-20, pp. 595--606, 2005.
• 19: J. Fridrich, M. Goljan, and T. Holotyak, "New Blind Steganalysis and its Implications," in Proc. SPIE, Electronic Imaging, Security, Steganography, and Watermarking of Multimedia Contents VIII, San Jose, CA, January 16-19, pp. 1--13, 2006.
• 20: A. Ker, "A General Framework for Structural Analysis of LSB Replacement," in M. Barni et al. (editors): Information Hiding. 7th International Workshop, Lecture Notes in Computer Science, vol. 3727, Springer-Verlag, New York, pp. 296--311, 2005.
• 21: J. Fridrich, "Feature-Based Steganalysis for JPEG Images and its Implications for Future Design of Steganographic Schemes", in J. Fridrich (editor): Information Hiding. 6th International Workshop, Lecture Notes in Computer Science, vol. 3200, Springer-Verlag, New York, pp. 67--81, 2004.
• 22: M. Kharrazi, H.T. Sencar, N.D. Memon: "Benchmarking Steganographic and Steganalytic Techniques," Proc. SPIE, Electronic Imaging, Security, Steganography, and Watermarking of Multimedia Contents VII, vol. 5681, San Jose, CA, January 16-20, pp. 252--263, 2005.
• 23: K. Sullivan, U. Madhow, B.S. Manjunath, S. Chandrasekaran, "Steganalysis for Markov Cover Data with Applications to Images," to appear in IEEE Transactions on Information Security and Forensics, vol. 1(2), June 2006.
• 24: Mercan Topkara , Umut Topkara , Mikhail J. Atallah , Cuneyt Taskiran , Eugene Lin , Edward J. Delp, A hierarchical protocol for increasing the stealthiness of steganographic methods, Proceedings of the 2004 workshop on Multimedia and security, September 20-21, 2004, Magdeburg, Germany [doi>10.1145/1022431.1022436]
• 25: Siwei Lyu , Hany Farid, Detecting Hidden Messages Using Higher-Order Statistics and Support Vector Machines, Revised Papers from the 5th International Workshop on Information Hiding, p.340-354, October 07-09, 2002
• 26: I. Avcibaş, M. Kharrazib, N. Memon, B. Sankur, "Image Steganalysis with Binary Similarity Measures," EURASIP JASP, No. 17, pp. 2749--2757, 2005.
• 27: J. Fridrich, "Improving Steganographic Security by Minimizing the Embedding Impact," submitted to SPIE Electronic Imaging, Security, Steganography and Watermarking of Multimedia Contents, San Jose, California, January 2007.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.0 General

General Terms:
Algorithms, Security, Theory

Keywords:
distortion, matrix embedding, perturbed quantization, steganalysis, steganography, syndrome coding