Paper 2001/016

Efficient Traitor Tracing Algorithms using List Decoding

Alice Silverberg, Jessica Staddon, and Judy Walker


We apply powerful, recently discovered techniques for the list decoding of error-correcting codes to the problem of efficiently tracing traitors. Traitor tracing schemes have been extensively studied for use as a piracy deterrent. In a widely studied model for protecting digital content, each user in the system is associated with a unique set of symbols. For example, the sets may be used to install a software CD or decrypt pay-TV content. The assignment of sets is done in such a way that if a bounded collection of sets is used to form a new set to enable piracy, at least one of the traitor sets can be identified by applying a traitor tracing algorithm to the newly formed set. Much work has focused on methods for constructing such traceability schemes, but the complexity of the traitor tracing algorithms has received little attention. A widely used traitor tracing algorithm, the TA algorithm, has a running time of $O(\n)$ in general, where $\n$ is number of sets in the system (e.g., the number of copies of the CD), and therefore is inefficient for large populations. In this paper we use a coding theoretic approach to produce traceability schemes for which the TA algorithm is very fast. We show that when suitable error-correcting codes are used to construct traceability schemes, and fast list decoding algorithms are used to trace, the run time of the TA algorithm is polynomial in the codeword length. We also use the strength of the error-correcting code approach to construct traceability schemes with more efficient algorithms for finding all possible traitor coalitions. Finally, we provide evidence that amongst traceability schemes in general, TA traceability schemes are the most likely to be amenable to efficient tracing methods.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
traceabilitytraitor tracinglist decodingerror-correcting codes
Contact author(s)
silver @ math ohio-state edu
2001-02-26: received
Short URL
Creative Commons Attribution


      author = {Alice Silverberg and Jessica Staddon and Judy Walker},
      title = {Efficient Traitor Tracing Algorithms using List Decoding},
      howpublished = {Cryptology ePrint Archive, Paper 2001/016},
      year = {2001},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.