Abstract.
Traitor tracing schemes constitute a useful tool against piracy in the context of digital content distribution. They are encryption schemes that can be employed by content providers that wish to deliver content to an exclusive set of users. Each user holds a decryption key that is fingerprinted and bound to his identity. When a pirate decoder is discovered, it is possible to trace the identities of the users that contributed to its construction. In most settings, both the user population and the set of content providers are dynamic, thus scalable user management and scalable provider management are crucial. Previous work on public-key traitor tracing did not address the dynamic scenario thoroughly: no efficient scalable public-key traitor tracing scheme has been proposed, in which the populations of providers and users can change dynamically over time without incurring substantial penalty in terms of system performance and management complexity. To address these issues, we introduce a formal model for Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and unlimited number of efficient provider and user management operations. We present a formal adversarial model for our system and we prove our construction secure, against both adversaries that attempt to cheat the provider and user management mechanism, and adversaries that attempt to cheat the traitor tracing mechanism.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Berlekamp ER, Welch LR: Error Correction of Algebraic Block Codes, 1986. U.S. Patent, Number 4,633,470
Bini D, Pan VY: Polynomial and Matrix Computations (vol. 1): Fundamental Algorithms. Birkhäuser, 1994
Boneh D, Franklin M: An Efficient Public Key Traitor Tracing Scheme. In: Advances in Cryptology - Crypto ‘99. LNCS 1666, pp 338-353. Springer, 1999. Full version available at crypto.stanford.edu/~dabo/pubs.html
Brands S: Rethinking Public Key Infrastructures and Digital Certificates - Building in Privacy. PhD thesis, Technical University of Eindhoven, 1999
Canetti R, Garay J, Itkis G, Micciancio D, Naor M, Pinkas B: Multicast Security: A Taxonomy and some Efficient Constructions. Proceedings of IEEE INFOCOM ‘99 2:708-716 (1999)
Chor B, Fiat A, Naor N: Tracing Traitors. In: Advances in Cryptology - Crypto ‘94 Springer, 1994, pp. 257-270. LNCS 839
Cramer R, Shoup V: Design and Analysis of Practical Public-Key Encryption Scheme Secure against Adaptive Chosen Ciphertext Attack. SIAM J Comput 33(1):167-226 (2003)
Dodis Y, Fazio N: Public-Key Broadcast Encryption for Statless Receivers. In: Digital Rights Management - DRM ‘02. LNCS 2696, pp. 61-80 Springer, 2002
Dodis Y, Fazio N: Public-Key Trace and Revoke Scheme Secure against Adaptive Chosen Ciphertext Attack. In: Public Key Cryptography - PKC ‘03. LNCS 2567, pp. 100-115. Springer, 2003
Dodis Y, Fazio N, Kiayias A, Yung M: Scalable Public-Key Tracing and Revoking. In: 22nd Annual Symposium on Principles of Distributed Computing - PODC ‘03, pp. 190-199. ACM Press, 2003
Dodis Y, Katz J, Xu S, Yung M: Key-Insulated Public-Key Cryptosystems. In: Advances in Cryptology - EuroCrypt ‘02. LNCS 2332, pp. 65-82. Springer, 2002
Fiat A, Naor M: Broadcast Encryption. In: Advances in Cryptology - Crypto ‘93. LNCS 773, pp. 480-491. Springer, 1993
Fiat A, Tassa T: Dynamic Traitor Tracing. J Cryptol 14(3):211-223 (2001)
Gafni E, Staddon J, Yin YL: Efficient Methods for Integrating Traceability and Broadcast Encryption. In: Advances in Cryptology - Crypto ‘99. LNCS 1666, pp. 372-387. Springer, 1999
Garay A, Staddon J, Wool A: Long-Lived Broadcast Encryption. In: Advances in Cryptology - Crypto 2000. LNCS 1880, pp. 333-352. Springer, 2000
Guruswami V, Sudan M: Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. In: IEEE Symposium on Foundations of Computer Science, pp. 28-39, 1998
Halevy D, Shamir A: The LSD Broadcast Encryption Scheme. In: Advances in Cryptology - Crypto ‘02. LNCS 2442, pp. 47-60. Springer, 2002
Kiayias A, Yung M: On Crafty Pirates and Foxy Tracers. In: Digital Rights Management - DRM ‘01. LNCS 2320, pp. 22-39. Springer, 2001
Kiayias A, Yung M: Self Protecting Pirates and Black-Box Traitor Tracing. In: Advances in Cryptology - Crypto ‘01. LNCS 2139, pp. 63-79. Springer, 2001
Kiayias A, Yung M: Traitor Tracing with Constant Transmission Rate. In: Advances in Cryptology - EuroCrypt ‘02. LNCS 2332, pp. 450-465. Springer, 2002
Kurosawa K, Desmedt Y: Optimum Traitor Tracing and new Direction for Asymmetricity. In: Advances in Cryptology - EuroCrypt ‘98. LNCS 1403, pp. 145-157. Springer, 1998
MacWilliams FJ, Sloane N: The Theory of Error Correcting Codes. North Holland, Amsterdam, 1977
Naor D, Naor M, Lotspiech J: Revocation and Tracing Schemes for Stateless Receivers. In: Advances in Cryptology - Crypto ‘01. LNCS 2139, pp. 41-62. Springer, 2001
Naor M, Pinkas B: Threshold Traitor Tracing. In: Advances in Cryptology - Crypto ‘98. LNCS 1462, pp. 502-517. Springer, 1998
Naor M, Pinkas B: Efficient Trace and Revoke Schemes. In: Financial Cryptography - FC 2000. LNCS 1962, pp. 1-20. Springer, 2000. Full version available at www.wisdom.weizmann.ac.il/~ naor/onpub.html
Ostrovsky R, Yung M: How to Withstand Mobile Virus Attacks. In: Logrippo L (ed) Proceedings of the 10th Annual ACM Symposium on Principles of Distributed Computing, pp. 51-60, Montréal, Québec, Canada, August 1991. ACM Press
Stinson DR, Wei R: Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes. SIAM J Discrete Math 11(1):41-53 (1998)
Tzeng WG, Tzeng ZJ: A Public-Key Traitor Tracing Scheme with Revocation Using Dynamics Shares. In: Public Key Cryptography - PKC ‘01. LNCS 1992, pp. 207-224. Springer, 2001
Wallner D, Harder E, Agee R: Key Management for Multicast: Issues and Architectures. Available at ftp://ftp.ietf.org/rfc/rfc2627.txt, 1997
Author information
Authors and Affiliations
Corresponding author
Additional information
Received: 28 August 2003, Accepted: 13 October 2004, Published online: 13 January 2005
Rights and permissions
About this article
Cite this article
Dodis, Y., Fazio, N., Kiayias, A. et al. Scalable public-key tracing and revoking. Distrib. Comput. 17, 323–347 (2005). https://doi.org/10.1007/s00446-004-0120-5
Issue Date:
DOI: https://doi.org/10.1007/s00446-004-0120-5