Collusion resistant traitor tracing systems




Goyal, Rishab

Journal Title

Journal ISSN

Volume Title



The notion of traitor tracing was introduced by Chor, Fiat, and Naor [47] in the early 90s with the goal of solving accountability problem in broadcast systems. While the original motivation was of catching users that create pirate decoder boxes in broadcast TV systems, there are several applications that go beyond that setting. Despite wide applicability of such systems all existing solutions for the traitor tracing problem suffer from one or more deficiencies (such as have large ciphertext size, or prove security in the bounded-collusion setting, or provide only weak tracing guarantees, or rely on strong cryptographic assumptions). In this proposed thesis, we provide the first traitor tracing scheme that does not suffer from any of the aforementioned deficiencies. That is, we provide a collusion resistant traitor tracing system 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 [107, 108]. This is the first traitor tracing scheme with such parameters provably secure from a standard cryptographic assumption. 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. In addition to achieving new traitor tracing results, the techniques developed push forward the broader area of computing on encrypted data under standard assumptions. Notably, traitor tracing is a substantially different problem from other cryptography primitives that have seen recent progress in LWE-based solutions. Additionally, we show that our techniques could be used to provide new constructions for traitor tracing systems with embedded identity tracing functionality [104] as well.


LCSH Subject Headings