Paper 2019/980

New Approaches to Traitor Tracing with Embedded Identities

Rishab Goyal, Venkata Koppula, and Brent Waters


In a traitor tracing (TT) system for $n$ users, every user has his/her own secret key. Content providers can encrypt messages using a public key, and each user can decrypt the ciphertext using his/her secret key. Suppose some of the $n$ users collude to construct a pirate decoding box. Then the tracing scheme has a special algorithm, called $Trace$, which can identify at least one of the secret keys used to construct the pirate decoding box. Traditionally, the trace algorithm output only the `index' associated with the traitors. As a result, to use such systems, either a central master authority must map the indices to actual identities, or there should be a public mapping of indices to identities. Both these options are problematic, especially if we need public tracing with anonymity of users. Nishimaki, Wichs, and Zhandry (NWZ) [Eurocrypt 2016] addressed this problem by constructing a traitor tracing scheme where the identities of users are embedded in the secret keys, and the trace algorithm, given a decoding box $D$, can recover the entire identities of the traitors. We call such schemes `Embedded Identity Traitor Tracing' schemes. NWZ constructed such schemes based on adaptively secure functional encryption (FE). Currently, the only known constructions of FE schemes are based on nonstandard assumptions such as multilinear maps and iO. In this work, we study the problem of embedded identities TT based on standard assumptions. We provide a range of constructions based on different assumptions such as public key encryption (PKE), bilinear maps and the Learning with Errors (LWE) assumption. The different constructions have different efficiency trade offs. In our PKE based construction, the ciphertext size grows linearly with the number of users; the bilinear maps based construction has sub-linear ($\sqrt{n}$) sized ciphertexts. Both these schemes have public tracing. The LWE based scheme is a private tracing scheme with optimal ciphertexts (i.e., $\log(n)$). Finally, we also present other notions of traitor tracing, and discuss how they can be build in a generic manner from our base embedded identity TT scheme.

Available format(s)
Public-key cryptography
Publication info
Published by the IACR in TCC 2019
traitor tracingpublic-key cryptography
Contact author(s)
rgoyal @ cs utexas edu
kvenkatavk @ gmail com
bwaters @ cs utexas edu
2019-08-29: received
Short URL
Creative Commons Attribution


      author = {Rishab Goyal and Venkata Koppula and Brent Waters},
      title = {New Approaches to Traitor Tracing with Embedded Identities},
      howpublished = {Cryptology ePrint Archive, Paper 2019/980},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.