Abstract
The informal goal of a watermarking scheme is to “mark” a digital object, such as a picture or video, in such a way that it is difficult for an adversary to remove the mark without destroying the content of the object. Although there has been considerable work proposing and breaking watermarking schemes, there has been little attention given to the formal security goals of such a scheme. In this work, we provide a new complexity-theoretic definition of security for watermarking schemes. We describe some shortcomings of previous attempts at defining watermarking security, and show that security under our definition also implies security under previous definitions. We also propose two weaker security conditions that seem to capture the security goals of practice-oriented work on watermarking and show how schemes satisfying these weaker goals can be strengthened to satisfy our definition.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Anderson, R.J.: Security Engineering: A Guide to Building Dependable Distributed Systems. John Wiley & Sons, Inc., New York (2001)
Cox, I., Miller, M.L., Bloom, J.A.: Digital watermarking. Morgan Kaufmann, San Francisco (2002)
Wong, P.W., Delp, E.J. (eds.): Proceedings of Security and Watermarking of Multimedia Contents. Proceedings of SPIE, vol. 3657. SPIE, Bellingham (1999)
Wong, P.W., Delp, E.J. (eds.): Proceedings of Security and Watermarking of Multimedia Contents II, 2000. Proceedings of SPIE, vol. 3971. SPIE, Bellingham (2000)
Wong, P.W., Delp, E.J. (eds.): Proceedings of Security and Watermarking of Multimedia Contents III, 2001. Proceedings of SPIE, vol. 4314. SPIE, Bellingham (2001)
Delp, E.J., Wong, P.W. (eds.): Proceedings of Security and Watermarking of Multimedia Contents IV, 2002. Proceedings of SPIE, vol. 4675. SPIE, Bellingham (2002)
Delp, E.J., Wong, P.W.: Proceedings of Security, Steganography, and Watermarking of Multimedia Contents V, 2003. Proceedings of SPIE, vol. 5020. SPIE, Bellingham (2003)
Delp, E.J., Wong, P.W. (eds.): Proceedings of Security, Steganography, and Watermarking of Multimedia Contents VI, San Jose, California, USA, January, 2004. Proceedings of SPIE, vol. 5306, pp. 18–22. SPIE, Bellingham (2004)
Delp, E.J., Wong, P.W. (eds.): Proceedings of Security, Steganography, and Watermarking of Multimedia Contents VII, San Jose, California, USA, January, 2005. Proceedings of SPIE, vol. 5681, pp. 17–20. SPIE, Bellingham (2005)
Anderson, R. (ed.): Information Hiding. LNCS, vol. 1174. Springer, Heidelberg (1996)
Aucsmith, D. (ed.): IH 1998. LNCS, vol. 1525. Springer, Heidelberg (1998)
Barni, M., Herrera-Joancomartí, J., Katzenbeisser, S., Pérez-González, F. (eds.): IH 2005. LNCS, vol. 3727. Springer, Heidelberg (2005)
Pfitzmann, A. (ed.): IH 1999. LNCS, vol. 1768. Springer, Heidelberg (2000)
Moskowitz, I.S. (ed.): Information Hiding. LNCS, vol. 2137. Springer, Heidelberg (2001)
Petitcolas, F.A.P. (ed.): IH 2002. LNCS, vol. 2578. Springer, Heidelberg (2003)
Fridrich, J. (ed.): IH 2004. LNCS, vol. 3200. Springer, Heidelberg (2004)
Gollmann, D.: Computer security. John Wiley & Sons, Inc., New York (1999)
Wikipedia: Digital watermarking — wikipedia, the free encyclopedia (2006), [Online; accessed 31-July-2006]
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001)
Lynn, B., Prabhakaran, M., Sahai, A.: Positive results and techniques for obfuscation. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 20–39. Springer, Heidelberg (2004)
Wee, H.: On obfuscating point functions. In: Gabow, H.N., Fagin, R. (eds.) STOC, pp. 523–532. ACM Press, New York (2005)
Cachin, C.: An information-theoretic model for steganography. In: Aucsmith, D. (ed.) IH 1998. LNCS, vol. 1525, pp. 306–318. Springer, Heidelberg (1998)
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)
Dedic, N., Itkis, G., Reyzin, L., Russell, S.: Upper and lower bounds on black-box steganography. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 227–244. Springer, Heidelberg (2005)
Craver, S., Memon, N., Yeo, B.L., Yeung, M.M.: Resolving rightful ownerships with invisible watermarking techniques: Limitations, attacks, and implications. IEEE J. SAC 16(4), 573–586, Special issue on copyright & privacy protection (1998)
Kutter, M., Voloshynovskiy, S., Herrigel, A.: The watermark copy attack. In: Security and Watermarking of Multimedia Contents II. Proceedings of the SPIE, vol. 3971, pp. 371–380. SPIE, Bellingham (2000)
Adelsbach, A., Katzenbeisser, S., Veith, H.: Watermarking schemes provably secure against copy and ambiguity attacks. In: DRM ’03: Proceedings of the 2003 ACM workshop on Digital rights management, pp. 111–119. ACM Press, New York (2003)
Dittmann, J., Katzenbeisser, S., Schallhart, C., Veith, H.: Provably secure authentication of digital media through invertible watermarks. Cryptology ePrint Archive, Report, 2004/293 (2004), http://eprint.iacr.org/
Li, Q., Chang, E.C.: On the possibility of non-invertible watermarking schemes. In: Fridrich, J. (ed.) IH 2004. LNCS, vol. 3200, Springer, Heidelberg (2004)
Hopper, N., Molnar, D., Wagner, D.: From weak to strong watermarking. IACR Cryptology ePrint Archive, Report, 2006/XXX (2006), http://eprint.iacr.org/2006/XXX
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
Bellare, M., Desai, A., Jokipii, E., Rogaway, P.: A concrete security treatment of symmetric encryption. In: Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS ’97), p. 394. IEEE Computer Society, Los Alamitos (1997)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)
Li, L., Pan, Z., Zhang, M., Ye, K.: Watermarking subdivision surfaces based on addition property of fourier transform. In: GRAPHITE ’04: Proceedings of the 2nd international conference on Computer graphics and interactive techniques in Australasia and South East Asia, pp. 46–49. ACM Press, New York (2004)
Meerwald, P., Uhl, A.: A survey of wavelet-domain watermarking algorithms. In: Wong, P.W., Delp, E.J. (eds.) Electronic Imaging, Security and Watermarking of Multimedia Contents III, San Jose, CA, USA, January. Proceedings of SPIE, vol. 4314, USA, Bellingham (2001)
Ruanaidh, J.J.O., Pereira, S.: A secure robust digital image watermark. In: International Symposium on Advanced Imaging and Network Technologies - Conference on Electronic Imaging: Processing, Printing, and Publishing in Colour (1998)
Moulin, P., Wang, Y.: Improved QIM strategies for gaussian watermarking. In: Barni, M., Cox, I., Kalker, T., Kim, H.J. (eds.) IWDW 2005. LNCS, vol. 3710, Springer, Heidelberg (2005)
Bas, P.: A quantization watermarking technique robust to linear and non-linear valumetric distortions using a fractal set of floating quantifiers. In: Information Hiding Workshop (IHW’05) (2005)
Martin, V., Chabert, M., Lacaze, B.: A spread spectrum watermarking scheme based on periodic clock changes for digital images. Information Hiding Workshop (IHW’05) (2005)
Doerr, G., Dugelay, J.L.: A quantization watermarking technique robust to linear and non-linear valumetric distortions using a fractal set of floating quantifiers. Information Hiding Workshop (IHW’05) (2005)
Hartung, F., Girod, B.: Fast public-key watermarking of compressed video. In: International Conference on Image Processing (ICIP’97), vol. 1, Santa Barbara, California, U.S.A, pp. 528–531 (1997)
Micali, S., Peikert, C., Sudan, M., Wilson, D.: Optimal error correction against computationally bounded noise. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, Springer, Heidelberg (2005), http://theory.lcs.mit.edu/~cpeikert/pubs/mpsw.ps
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, Springer, Heidelberg (2001)
Wong, P.W., Memon, N.: Secret and public key image watermarking schemes for image authentication and ownership verification. IEEE Trans. Image Processing 10(10), 1593–1601 (2001)
Petitcolas, F.A., Anderson, R.J., Kuhn, M.G.: Attacks on copyright marking systems. In: Aucsmith, D. (ed.) IH 1998. LNCS, vol. 1525, pp. 219–239. Springer, Heidelberg (1998)
Petitcolas, F.A.: Watermarking schemes evaluation. IEEE Signal Processing 17(4), 58–64 (2000)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Hopper, N., Molnar, D., Wagner, D. (2007). From Weak to Strong Watermarking. In: Vadhan, S.P. (eds) Theory of Cryptography. TCC 2007. Lecture Notes in Computer Science, vol 4392. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-70936-7_20
Download citation
DOI: https://doi.org/10.1007/978-3-540-70936-7_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-70935-0
Online ISBN: 978-3-540-70936-7
eBook Packages: Computer ScienceComputer Science (R0)