Paper 2012/088

A Lattice-Based Traitor Tracing Scheme

San Ling and Damien Stehle

Abstract

A traitor tracing scheme is a multi-receiver encryption scheme where malicious receiver coalitions aiming at building pirate decryption devices are deterred by the existence of a tracing algorithm: Using the pirate decryption device, the tracing algorithm can recover at least one member of the malicious coalition. All existing traitor tracing schemes rely either on rather inefficient generic constructions from arbitrary encryption schemes and collusion-secure fingerprinting codes, or on algebraic constructions exploiting the assumed hardness of variants of the Discrete Logarithm Problem. In this work, we present the first algebraic construction of a traitor tracing encryption scheme whose security relies on the assumed (quantum) worst-case hardness of standard lattice problems. The scheme is public-key, provably resists Chosen Plaintext Attacks and allows for minimal access black-box tracing (i.e., tracing works even if granted a very limited access to the pirate decryption device). It inherits the standard features of lattice-based cryptography, such as provable security under mild computational assumptions, conjectured resistance to quantum computers, and asymptotic efficiency. For proving the security, we introduce a Learning With Errors variant of the k-SIS problem from Boneh and Freeman [PKC'11], which we prove at least as hard as the standard LWE problem. We also describe a variant of our scheme with security based on the assumed hardness of the Ring Learning With Errors problem which achieves quasi-optimal asymptotic performance with respect to the security parameter.