Optimal probabilistic fingerprint codes

ABSTRACT

We construct binary codes for fingerprinting. Our codes for n users that are ε-secure against c pirates have length O(c² log(n/ε)). This improves the codes proposed by Boneh and Shaw [3] whose length is approximately the square of this length. Our codes are probabilistic. By proving matching lower bounds we establish that the length of these codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert, Shelat, and Smith [10] that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet, and also the equal strength of two distinct models for fingerprinting.

REFERENCES

• 1: G. R. Blakley , Catherine Meadows , George B. Purdy, Fingerprinting Long Forgiving Messages, Advances in Cryptology, p.180-189, August 18-22, 1985
• 2: Dan Boneh , Matthew K. Franklin, An Efficient Public Key Traitor Tracing Scheme, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.338-353, August 15-19, 1999
• 3: D. Boneh and J. Shaw, Collusion-secure fingerprinting for digital data, IEEE Transactions of Information Theory 44 (1998), 480--491.
• 4: F. Chung, R. Graham, T. Leighton, Guessing secrets, Electronic Journal of Combinatorics 8 (1), 2001.
• 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: Hans-Jürgen Guth , Birgit Pfitzmann, Error- and Collusion-Secure Fingerprinting for Digital Data, Proceedings of the Third International Workshop on Information Hiding, p.134-145, September 29-October 01, 1999
• 7: J. Kilian, T. Leighton, L. Matheson, T. Shamoon, R. Tarjan, F. Zane, Resistance of digital watermarks to collusive attacks, in: Proceedings of 1998 IEEE International Symposium on Information Theory.
• 8: K. Kurosawa and Y. Desmedt, Optimum traitor tracing and asymmetric schemes, Advances in cryptology---EUROCRYPT'98 LNCS 1403, Springer, Berlin, 1998, pp. 145--157.
• 9: T. Lindkvist, Fingerprinting digital documents, Linköping Studies in Science and Technology, Thesis No. 798, 1999.
• 10: Chris Peikert , Abhi shelat , Adam Smith, Lower bounds for collusion-secure fingerprinting, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 11: A. Rényi, Probability theory, North-Holland Series in Applied Mathematics and Mechanics, Vol. 10. North-Holland Publishing Co., Amsterdam, London; American Elsevier Publishing Co., Inc., New York, 1970.
• 12: Reihaneh Safavi-Naini , Yejing Wang, Sequential Traitor Tracing, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.316-332, August 20-24, 2000
• 13: J. N. Staddon, D. R. Stinson, R. Wei, Combinatorial properties of frameproof and traceability codes, IEEE Transactions of Information Theory 47 (2001), 1042--1049.
• 14: Neal R. Wagner, Fingerprinting, Proceedings of the 1983 IEEE Symposium on Security and Privacy, p.18, April 25-27, 1983

INDEX TERMS

Primary Classification:
  E. Data
  E.3 DATA ENCRYPTION
      Subjects: Standards (e.g., DES, PGP, RSA)

General Terms:
Security, Theory

Keywords:
collusion-secure codes, cryptography, fingerprint