Paper 2018/346

Collusion Resistant Traitor Tracing from Learning with Errors

Rishab Goyal, Venkata Koppula, and Brent Waters


In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in $\log(n)$ where $n$ is the number of users and prove it secure under the Learning with Errors (LWE) assumption. This is the first traitor tracing scheme with such parameters provably secure from a standard assumption. In addition to achieving new traitor tracing results, we believe our techniques push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is substantially different problem from other cryptography primitives that have seen recent progress in LWE solutions. We achieve our results by first conceiving a novel approach to building traitor tracing that starts with a new form of Functional Encryption that we call Mixed FE. In a Mixed FE system the encryption algorithm is bimodal and works with either a public key or master secret key. Ciphertexts encrypted using the public key can only encrypt one type of functionality. On the other hand the secret key encryption can be used to encode many different types of programs, but is only secure as long as the attacker sees a bounded number of such ciphertexts. We first show how to combine Mixed FE with Attribute-Based Encryption to achieve traitor tracing. Second we build Mixed FE systems for polynomial sized branching programs (which corresponds to the complexity class LOGSPACE) by relying on the polynomial hardness of the LWE assumption with super-polynomial modulus-to-noise ratio.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. STOC 2018
Traitor TracingLWE
Contact author(s)
rgoyal @ cs utexas edu
2018-04-16: received
Short URL
Creative Commons Attribution


      author = {Rishab Goyal and Venkata Koppula and Brent Waters},
      title = {Collusion Resistant Traitor Tracing from Learning with Errors},
      howpublished = {Cryptology ePrint Archive, Paper 2018/346},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.