Anonymous traitor tracing: How to embed arbitrary information in a key

Ryo Nishimaki, Daniel Wichs, Mark Zhandry

Research output: Chapter in Book/Report/Conference proceedingConference contribution

34 Scopus citations


In a traitor tracing scheme, each user is given a different decryption key. A content distributor can encrypt digital content using a public encryption key and each user in the system can decrypt it using her decryption key. Even if a coalition of users combines their decryption keys and constructs some “pirate decoder” that is capable of decrypting the content, there is a public tracing algorithm that is guaranteed to recover the identity of at least one of the users in the coalition given black-box access to such decoder. In prior solutions, the users are indexed by numbers 1,…, N and the tracing algorithm recovers the index i of a user in a coalition. Such solutions implicitly require the content distributor to keep a record that associates each index i with the actual identifying information for the corresponding user (e.g., name, address, etc.) in order to ensure accountability. In this work, we construct traitor tracing schemes where all of the identifying information about the user can be embedded directly into the user’s key and recovered by the tracing algorithm. In particular, the content distributor does not need to separately store any records about the users of the system, and honest users can even remain anonymous to the content distributor. The main technical difficulty comes in designing tracing algorithms that can handle an exponentially large universe of possible identities, rather than just a polynomial set of indices i ∈ [N]. We solve this by abstracting out an interesting algorithmic problem that has surprising connections with seemingly unrelated areas in cryptography. We also extend our solution to a full “broadcast-trace-and-revoke” scheme in which the traced users can subsequently be revoked from the system. Depending on parameters, some of our schemes can be based only on the existence of public-key encryption while others rely on indistinguishability obfuscation.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
EditorsMarc Fischlin, Jean-Sebastien Coron
PublisherSpringer Verlag
Number of pages32
ISBN (Print)9783662498958
StatePublished - 2016
Event35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016 - Vienna, Austria
Duration: May 8 2016May 12 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Anonymous traitor tracing: How to embed arbitrary information in a key'. Together they form a unique fingerprint.

Cite this