Overcoming the obstacles of zero-knowledge watermark detection

ABSTRACT

Standard watermarking schemes suffer from a major problem: They require to reveal security critical information to potentially untrusted parties, when proving the presence of a watermark to these parties. Zero-knowledge watermark detection is a promising means to overcome this problem and to improve the security of digital watermarking schemes in the context of various applications: it allows to cryptographically conceal the information required for the detection of a watermark and to prove the presence of the hidden watermark by efficient zero-knowledge proof systems.However, concealing the watermark prevents the verifying party from performing additional checks on the watermark, e.g., on its probability distribution, which may be required for certain applications. This is a limitation in the use of zero-knowledge watermark detection and we present several strategies to overcome this issue.Furthermore, we propose concrete and practical protocols, which pursue two promising strategies: the first strategy is to prove in zero-knowledge that a concealed watermark suffices a certain desired distribution, whereas the second strategy is to interactively and verifiably generate watermarks that suffice the desired distribution.

REFERENCES

• 1: André Adelsbach, Stefan Katzenbeisser, and Ahmad-Reza Sadeghi. Watermark detection with zero-knowledge disclosure. ACM Multimedia Systems Journal, 9(3):266--278, September 2003. Special Issue on Multimedia Security.
• 2: André Adelsbach, Stefan Katzenbeisser, and Ahmad-Reza Sadeghi. On the insecurity of non-invertible watermarking schemes for dispute resolving. In International Workshop on Digital Watermarking, IWDW 2003, volume 2939 of Lecture Notes in Computer Science, pages 355--369. Springer-Verlag, Berlin Germany, 2004.
• 3: André Adelsbach , Birgit Pfitzmann , Ahmad-Reza Sadeghi, Proving Ownership of Digital Content, Proceedings of the Third International Workshop on Information Hiding, p.117-133, September 29-October 01, 1999
• 4: André Adelsbach , Ahmad-Reza Sadeghi, Zero-Knowledge Watermark Detection and Proof of Ownership, Proceedings of the 4th International Workshop on Information Hiding, p.273-288, April 25-27, 2001
• 5: André Adelsbach and Ahmad-Reza Sadeghi. Advanced techniques for dispute resolving and authorship proofs on digital works. In Proceedings of SPIE Vol. 5020, Security and Watermarking of Multimedia Contents V, 2003.
• 6: J. H. Ahrens , U. Dieter, Computer methods for sampling from the exponential and normal distributions, Communications of the ACM, v.15 n.10, p.873-882, Oct. 1972 [doi>10.1145/355604.361593]
• 7: Fabrice Boudot. Efficient proofs that a committed number lies in an interval. In Bart Preneel, editor, Advances in Cryptology -- EUROCRYPT '2000, volume 1807 of Lecture Notes in Computer Science, pages 431--444, Brugge, Belgium, 2000. Springer-Verlag, Berlin Germany.
• 8: Gilles Brassard , David Chaum , Claude Crépeau, Minimum disclosure proofs of knowledge, Journal of Computer and System Sciences, v.37 n.2, p.156-189, October 1988 [doi>10.1016/0022-0000(88)90005-0]
• 9: Jan Camenisch and Markus Michels. Proving in zero-knowledge that a number is the product of two safe primes. In Jacques Stern, editor, Advances in Cryptology -- EUROCRYPT '99, volume 1599 of Lecture Notes in Computer Science, pages 107--122. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 1999.
• 10: D. Chaum, J.-H. Evertse, and J. van de Graaf. An improved protocol for demonstrating possession of discrete logarithms and some generalizations. In David Chaum and Wyn~L. Price, editors, Advances in Cryptology -- EUROCRYPT '87, volume 304 of Lecture Notes in Computer Science, pages 127--141. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 1988.
• 11: David Chaum , Eugène van Heijst , Birgit Pfitzmann, Cryptographically Strong Undeniable Signatures, Unconditionally Secure for the Signer, Proceedings of the 11th Annual International Cryptology Conference on Advances in Cryptology, p.470-484, August 11-15, 1991
• 12: R Cleve, Limits on the security of coin flips when half the processors are faulty, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.364-369, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12168]
• 13: Ingemar J. Cox , Joe Kilian , Frank Thomson Leighton , Talal Shamoon, A Secure, Robust Watermark for Multimedia, Proceedings of the First International Workshop on Information Hiding, p.185-206, May 30-June 01, 1996
• 14: Ingemar Cox , Matthew L. Miller , Jeffery A. Bloom, Digital watermarking, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 15: Scott Craver, Zero Knowledge Watermark Detection, Proceedings of the Third International Workshop on Information Hiding, p.101-116, September 29-October 01, 1999
• 16: Scott Craver, Bede Liu, and Wayne Wolf. An implementation of, and attacks on, zero-knowledge watermarking. In Accepted for Information Hiding Workshop 2004, 2004.
• 17: Scott Craver, Nasir Memon, Boon-Lock Yeo, and Minerva M. Yeung. Resolving rightful ownerships with invisible watermarking techniques: Limitations, attacks, and implications. IEEE Journal on Selected Areas in Communications, 16(4):573--586, May 1998.
• 18: Ivan Damgård, Commitment Schemes and Zero-Knowledge Protocols, Lectures on Data Security, Modern Cryptology in Theory and Practice, Summer School, Aarhus, Denmark, July 1998, p.63-86, January 1999
• 19: Ivan Damgård , Eiichiro Fujisaki, A Statistically-Hiding Integer Commitment Scheme Based on Groups with Hidden Order, Proceedings of the 8th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.125-142, December 01-05, 2002
• 20: J. J. Eggers, J. K. Su, and B. Girod. Asymmetric watermarking schemes. In Sicherheit in Netzen und Medienströmen, Springer Reihe, Informatik Aktuell, September 2000.
• 21: Eiichiro Fujisaki , Tatsuaki Okamoto, Statistical Zero Knowledge Protocols to Prove Modular Polynomial Relations, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.16-30, August 17-21, 1997
• 22: Eiichiro Fujisaki and Tatsuaki Okamoto. Statistical zero-knowledge protocols to prove modular relations. IEICE Transactions on Fundamentals, E82-A(1):81--92, Jan 1999.
• 23: Teddy Furon , Pierre Duhamel, An Asymmetric Public Detection Watermarking Technique, Proceedings of the Third International Workshop on Information Hiding, p.88-100, September 29-October 01, 1999
• 24: Oded Goldreich, Foundations of Cryptography: Basic Tools, Cambridge University Press, New York, NY, 2000
• 25: Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
• 26: K. Gopalakrishnan, N. Memon, and P. Vora. Protocols for watermark verification. In Multimedia and Security, Workshop at ACM Multimedia, pages 91--94, 1999.
• 27: A. J. Kinderman , J. F. Monahan, Computer Generation of Random Variables Using the Ratio of Uniform Deviates, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.257-260, Sept. 1977 [doi>10.1145/355744.355750]
• 28: Joseph L. Leva, A fast normal random number generator, ACM Transactions on Mathematical Software (TOMS), v.18 n.4, p.449-453, Dec. 1992 [doi>10.1145/138351.138364]
• 29: Helger Lipmaa. On diophantine complexity and statistical zero-knowledge arguments. In C.S. Laih, editor, Advances in Cryptology -- ASIACRYPT '2003, volume 2894 of Lecture Notes in Computer Science, pages 398--415. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 2003.
• 30: Fabien A. P. Petitcolas , Ross J. Anderson , Markus G. Kuhn, Attacks on Copyright Marking Systems, Proceedings of the Second International Workshop on Information Hiding, p.218-238, April 14-17, 1998
• 31: Andreas Pfitzmann, editor. Information Hiding---3rd International Workshop, IH'99, volume 1768 of Lecture Notes in Computer Science, Dresden, Germany, October 2000. Springer-Verlag, Berlin Germany.
• 32: Birgit Pfitzmann and Matthias Schunter. Asymmetric fingerprinting (extended abstract). In Ueli Maurer, editor, Advances in Cryptology -- EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 84--95. International Association for Cryptologic Research, Springer-Verlag, Berlin Germany, 1996.
• 33: Birgit Pfitzmann , Michael Waidner, Asymmetric fingerprinting for larger collusions, Proceedings of the 4th ACM conference on Computer and communications security, p.151-160, April 01-04, 1997, Zurich, Switzerland [doi>10.1145/266420.266453]
• 34: Mahalingam Ramkumar and Ali Akansu. Image watermarks and counterfeit attacks : Some problems and solutions. In Content Security and Data Hiding in Digital Media, 1999.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Security

Additional Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Public key cryptosystems

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce
          Subjects: Intellectual property

General Terms:
Security

Keywords:
interactive generation of commitments on Gaussian distributed samples, statistical tests on committed numbers, zero-knowledge protocols, zero-knowledge watermark detection