Lower bounds for collusion-secure fingerprinting

ABSTRACT

Collusion-secure fingerprinting codes are an important primitive used by many digital watermarking schemes [1, 10, 9]. Boneh and Shaw [3] define a model for these types of codes and present an explicit construction. Their code has length O(c³ log(l/ε)) and attains security against coalitions of size c with ε error. Boneh and Shaw also present a lower bound of Ω (c³log(1/cε)) on the length of any collusion-secure code.We give new lower bounds on the length of collusion-secure codes by analyzing a weighted coinflipping strategy for the coalition. As an illustration of our methods, we give a simple proof that the Boneh-Shaw construction cannot be asymptotically improved. Next, we prove a general lower bound: no secure code can have length O(c²1og(1/cε)), which improves the previous known bound by a factor of c. In particular, we show that any secure code will have length Ω(c² log(1/cε)) as long as log(l/ε) ≥ K k log c, where K is a constant and k is the number of columns in the code (in some sense, a measure of the code's complexity). Finally, we describe a general paradigm for constructing fingerprinting codes which encompasses the construction of [3], and show that no secure code that follows this paradigm can have length O((c³/log c) log(1/cε)) follows this (again, by showing a lower bound for large values of ln(1/ε)). This suggests that any attempts at improvement should be directed toward techniques that lie outside our paradigm.

REFERENCES

• 1: G R Blakley , Catherine Meadows , G B Purdy, Fingerprinting long forgiving messages, Lecture notes in computer sciences; 218 on Advances in cryptology---CRYPTO 85, p.180-189, June 1986, Santa Barbara, California, United States
• 2: B. Bollobás. Combinatorics. Cambridge University Press, 1986.
• 3: D. Boneh and J. Shaw. "Collusion-secure fingerprinting for digital data," IEEE Transactions on Information Theory, vol IT-44, Sep. 1998, pp. 1897--1905.
• 4: Jan Camenisch, Efficient Anonymous Fingerprinting with Group Signatures, Proceedings of the 6th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.415-428, December 03-07, 2000
• 5: Benny Chor , Amos Fiat , Moni Naor, Tracing Traitors, Proceedings of the 14th Annual International Cryptology Conference on Advances in Cryptology, p.257-270, August 21-25, 1994
• 6: Imre Csiszar , Janos G. Korner, Information Theory: Coding Theorems for Discrete Memoryless Systems, Academic Press, Inc., Orlando, FL, 1982
• 7: Joe Kilian, F. Thomson Leighton, Lesley R. Matheson, Talal G. Shamoon, Robert E. Tarjan, and Francis Zane. "Resistance of digital fingerprints to collusional attacks." Proceedings of 1998 IEEE International Symposium on Information Theory. Cambridge, MA, 16--21 August 1998, p. 271.
• 8: Tina Lindkvist. "Fingerprinting of digital documents," Dissertation No 706, Linköping University, September 2001.
• 9: 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]
• 10: B. Pfitzmann and M. Waidner. 'Anonymous fingerprinting." In Walter Fumy, editor, Advances in Cryptology-- EUROCRYPT'97, LNCS 1233, Springer-Verlag, Berlin, 1997, pp. 88--102.
• 11: Alice Silverberg , Jessica Staddon , Judy L. Walker, Efficient Traitor Tracing Algorithms Using List Decoding, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.175-192, December 09-13, 2001
• 12: Yacov Yacobi, Improved Boneh-Shaw Content Fingerprinting, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.378-391, April 08-12, 2001

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)
          Subjects: Authentication

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Security, Theory