Paper 2014/494
Hardness of k-LWE and Applications in Traitor Tracing
San Ling, Duong Hieu Phan, Damien Stehle, and Ron Steinfeld
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 worst-case 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 new lattice tools and the projective sampling family are quite general that they may have applications in other areas.
Note: Simplified and improved the reduction from LWE to k-LWE
Metadata
- Available format(s)
-
PDF
- Publication info
- A major revision of an IACR publication in CRYPTO 2014
- Contact author(s)
- damien stehle @ gmail com
- History
- 2015-08-05: last of 2 revisions
- 2014-06-26: received
- See all versions
- Short URL
- https://ia.cr/2014/494
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2014/494,
author = {San Ling and Duong Hieu Phan and Damien Stehle and Ron Steinfeld},
title = {Hardness of k-LWE and Applications in Traitor Tracing},
howpublished = {Cryptology ePrint Archive, Paper 2014/494},
year = {2014},
note = {\url{https://eprint.iacr.org/2014/494}},
url = {https://eprint.iacr.org/2014/494}
}
