Scalable public-key tracing and revoking

ABSTRACT

Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non trusted content providers using the same set of keys, which makes the scheme "server-side scalable." To make such schemes also "client-side scalable," i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations.To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an efficient new-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.

REFERENCES

• 1: E. Berlekamp and L. Welch. Error Correction of Algebraic Block Codes, 1986. U.S. Patent, Number 4,633,470.
• 2: Dario Bini , Victor Y. Pan, Polynomial and matrix computations (vol. 1): fundamental algorithms, Birkhauser Verlag, Basel, Switzerland, 1994
• 3: 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
• 4: 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
• 5: S. Brands. Rethinking Public Key Infrastructures and Digital Certificates --- Building in Privacy. PhD thesis, Technical University of Eindhoven, 1999.
• 6: R. Canetti, J. Garay, G. Itkis, D. Micciancio, M. Naor, and B. Pinkas. Multicast Security: A Taxonomy and some Efficient Constructions. In Proceedings of IEEE INFOCOM '99, volume 2, pages 708--716, 1999.
• 7: 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
• 8: R. Cramer and V. Shoup. Design and Analysis of Practical Public-Key Encryption Scheme Secure against Adaptive Chosen Ciphertext Attack. Manuscript, 2001.
• 9: Y. Dodis and N. Fazio. Public Key Broadcast Encryption for Statless Receivers. In Digital Rights Management - DRM '02, 2002.
• 10: 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
• 11: Amos Fiat , Moni Naor, Broadcast encryption, Proceedings of the 13th annual international cryptology conference on Advances in cryptology, p.480-491, January 1994, Santa Barbara, California, United States
• 12: 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
• 13: 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
• 14: 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
• 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: K. Kurosawa and Y. Desmedt. Optimum Traitor Tracing and new Direction for Asymmetricity. In Advances in Cryptology - EuroCrypt '98, pages 145--157. Springer-Verlag, 1998. LNCS 1403.
• 17: F. J. MacWilliams and N. Sloane. The Theory of Error Correcting Codes. North Holland, Amsterdam, 1977.
• 18: 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
• 19: Moni Naor , Benny Pinkas, Threshold Traitor Tracing, Proceedings of the 18th Annual International Cryptology Conference on Advances in Cryptology, p.502-517, August 23-27, 1998
• 20: 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
• 21: 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]
• 22: Wen-Guey Tzeng , Zhi-Jia Tzeng, A Public-Key Traitor Tracing Scheme with Revocation Using Dynamic Shares, Proceedings of the 4th International Workshop on Practice and Theory in Public Key Cryptography: Public Key Cryptography, p.207-224, February 13-15, 2001
• 23: D. Wallner, E. Harder, and R. Agee. Key Management for Multicast: Issues and Architectures. Available at ftp://ftp.ietf.org/rfc/rfc2627.txt, 1997.

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

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Performance, Security

Keywords:
Broadcast Encryption, Digital Content Distribution, Multicast, Scalability, Traitor Tracing