Scalable public-key tracing and revoking

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.