A lattice-based traitor
tracing scheme
San Ling, Duong Hieu Phan, Damien Stehlé and San Ling
Abstract: We introduce the k-LWE problem, a Learning With Errors variant of the k-SIS problem.
The Boneh-Freeman reduction from SIS to k-SIS suffers from an exponential loss in k. We improve
and extend it to an LWE to k-LWE reduction with a polynomial loss in k, by relying on a new
technique involving trapdoors for random integer kernel lattices. Based on this hardness result, we
present the first algebraic construction of a traitor tracing scheme whose security relies on the worstcase
hardness of standard lattice problems.
The proposed LWE traitor tracing is almost as efficient as the LWE encryption. Further, it achieves
public traceability, i.e., allows the authority to delegate the tracing capability to untrusted parties.
To this aim, we introduce the notion of projective sampling family in which each sampling function
is keyed and, with a projection of the key on a well chosen space, one can simulate the sampling
function in a computationally indistinguishable way. The construction of a projective sampling family
from k-LWE allows us to achieve public traceability, by publishing the projected keys of the users.
We believe that the k-LWE problem and the projective sampling family are quite general that they
may have applications in other areas.
Download: pdf.
Homepage