Public-key traitor tracing from efficient decoding and unbounded enrollment: extended abstract

ABSTRACT

Public-key traitor-tracing schemes is a supporting technology for content distribution that discourages abuse and resale of cryptographic keys used for the distribution. These schemes enable a system manager to maintain a set of subscribers so that any external content provider can use the public key nature of the method and transmit data to the subscribers, while assuring that if a coalition of users generate a pirate deciphering device, they can be identified via a procedure called "traitor tracing."

The usefulness of efficient decoding in this context was exemplified in the work of Boneh and Franklin that showed how a specific family of codes can be combined with ElGamal encryption to produce a public-key traitor tracing scheme that supports non-black-box traitor tracing and recovers all traitors that contributed to the pirate key.

In this work we are motivated by the notion of "Traitor Tracing with unbounded enrollment" that we define here, and we look for proper implementation thereof. To this end, we first generalize the Boneh Franklin approach to arbitrary code families by introducing Extended ElGamal encryption and showing an explicit condition under which the encryption can be transformed to traitor tracing, while also identifying cases where such transformation would not work; the properties are presented in terms of efficient decoding algorithms. The approach sheds light on the superlogarithmic (non-black-box) traceability of the Kurosawa-Desmedt public-key traitor tracing scheme that was only shown to support efficient tracing for a logarithmic number of traitors (in the black-box sense, where it was shown that logarithmic is optimal). Recall that the original non-black-box tracing algorithm of this scheme was found to be insufficient. We also show how to take advantage of list decoding techniques for non-black-box traitor tracing to extend the number of traitors that can be successfully traced. Finally, the Kurosawa Desmedt scheme accompanied with our tracing method is shown to be the first construction to implement traitor tracing with unbounded enrollment for an optimal number of traitors (for such a scheme) in both the non-black-box tracing case and the black-box tracing case.

REFERENCES

• 1: Elwyn R. Berlekamp and L. Welch, Error Correction of Algebraic Block Codes. U.S. Patent, Number 4, 633, 470 1986.
• 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: Dan Boneh and Matthew Franklin, An Efficient Public Key Traitor Tracing Scheme, manuscript, full-version of {2}, 2001.
• 4: Dan Boneh, Amit Sahai and Brent Waters, Fully Collusion Resistant Traitor Tracing with Short Ciphertexts and Private Keys, EUROCRYPT 2006, pp. 573--592.
• 5: Stefan Brands, Rethinking Public Key Infrastructures and Digital Certificates - Building in Privacy, Ph.D. thesis, Technical University of Eindhoven, 1999.
• 6: 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
• 7: Benny Chor, Amos Fiat, Moni Naor, and Benny Pinkas, Tracing Traitors,IEEE Transactions on Information Theory, Vol. 46, no. 3, pp. 893--910, 2000.
• 8: Joan Daemen , Vincent Rijmen, The Design of Rijndael, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 9: Yevgeniy Dodis , Nelly Fazio, Public Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack, Proceedings of the 6th International Workshop on Theory and Practice in Public Key Cryptography: Public Key Cryptography, p.100-115, January 06-08, 2003
• 10: Eli Gafni , Jessica Staddon , Yiqun Lisa Yin, Efficient Methods for Integrating Traceability and Broadcast Encryption, Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, p.372-387, August 15-19, 1999
• 11: Juan A. Garay , Jessica Staddon , Avishai Wool, Long-Lived Broadcast Encryption, Proceedings of the 20th Annual International Cryptology Conference on Advances in Cryptology, p.333-352, August 20-24, 2000
• 12: Venkatesan Guruswami , Madhu Sudan, Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.28, November 08-11, 1998
• 13: Dani Halevy , Adi Shamir, The LSD Broadcast Encryption Scheme, Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology, p.47-60, August 18-22, 2002
• 14: Nam-Su Jho, Jung Yeon Hwang, Jung Hee Cheon, Myung-Hwan Kim, Dong Hoon Lee, Eun Sun Yoo: One-Way Chain Based Broadcast Encryption Schemes. EUROCRYPT 2005: 559--574.
• 15: Aggelos Kiayias , Moti Yung, Self Protecting Pirates and Black-Box Traitor Tracing, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.63-79, August 19-23, 2001
• 16: Aggelos Kiayias , Moti Yung, Traitor Tracing with Constant Transmission Rate, Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques: Advances in Cryptology, p.450-465, May 02, 2002
• 17: Aggelos Kiayias , Moti Yung, On Crafty Pirates and Foxy Tracers, Revised Papers from the ACM CCS-8 Workshop on Security and Privacy in Digital Rights Management, p.22-39, November 05, 2001
• 18: Aggelos Kiayias , Stathis Zachos , Moti Yung, Polynomial reconstruction based cryptography, City University of New York, New York, NY, 2002
• 19: K. Kurosawa and Y. Desmedt, Optimum Traitor Tracing and Asymmetric Schemes,Advances in Cryptology - EUROCRYPT'98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 - June 4, 1998, Proceeding. Lecture Notes in Computer Science 1403 Springer 1998, pp. 145--157.
• 20: K. Kurosawa, M. Burmester and Y. Desmedt, A proven secure tracing algorithm for the optimal KD traitor tracing scheme, DIMACS Workshop on Management of Digital Intellectual Properties April 17--18, 2000.
• 21: Kaoru Kurosawa , Takuya Yoshida, Linear Code Implies Public-Key Traitor Tracing, Proceedings of the 5th International Workshop on Practice and Theory in Public Key Cryptosystems: Public Key Cryptography, p.172-187, February 12-14, 2002
• 22: F. J. MacWilliams and N. Sloane, The Theory of Error Correcting Codes. North Holland, Amsterdam, 1977.
• 23: Robert J. McEliece, On the Average List Size for the Guruswami-Sudan Decoder, 7th International Symposium on Communications Theory and Applications 2003.
• 24: Dalit Naor , Moni Naor , Jeffrey B. Lotspiech, Revocation and Tracing Schemes for Stateless Receivers, Proceedings of the 21st Annual International Cryptology Conference on Advances in Cryptology, p.41-62, August 19-23, 2001
• 25: Moni Naor , Benny Pinkas, Efficient Trace and Revoke Schemes, Proceedings of the 4th International Conference on Financial Cryptography, p.1-20, February 20-24, 2000
• 26: Reinaneh Safavi-Naini and Vu Dong To,Linear Code Implies Public-Key Traitor Tracingwith Revocation. Information Security and Privacy: 9th Australasian Conference, ACISP 2004, Sydney, Australia, July 13--15, 2004. Proceedings. Lecture Notes in Computer Science 3108 Springer 2004, pp.24--35.
• 27: 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
• 28: Douglas R. Stinson , R. Wei, Key Preassigned Traceability Schemes for Broadcast Encryption, Proceedings of the Selected Areas in Cryptography, p.144-156, August 17-18, 1998
• 29: D. R. Stinson , R. Wei, Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes, SIAM Journal on Discrete Mathematics, v.11 n.1, p.41-53, Feb. 1998 [doi>10.1137/S0895480196304246]
• 30: Dongvu Tonien, Reihaneh Safavi-Naini: An Efficient Single-Key Pirates Tracing Scheme Using Cover-Free Families. Applied Cryptography and Network Security, 4th International Conference, ACNS 2006, Singapore, June 6--9, 2006, Proceedings. Lecture Notes in Computer Science 3989, pp. 82--97.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Algorithms, Security

Keywords:
error correcting codes, traitor tracing