Hardness of k-LWE and applications in traitor tracing

San Ling, Duong Hieu Phan, Damien Stehlé, Ron Steinfeld

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

20 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2014
Subtitle of host publication34th Annual Cryptology Conference, Proceedings
EditorsJuan A. Garay, Rosario Gennaro
Place of PublicationHeidelberg
PublisherSpringer, Springer Nature
Pages315-334
Number of pages20
Volume8616 LNCS
EditionPART 1
ISBN (Electronic)9783662443712
ISBN (Print)9783662443705
DOIs
Publication statusPublished - 2014
Event34rd Annual International Cryptology Conference, CRYPTO 2014 - Santa Barbara, CA, United States
Duration: 17 Aug 201421 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
NumberPART 1
Volume8616 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other34rd Annual International Cryptology Conference, CRYPTO 2014
CountryUnited States
CitySanta Barbara, CA
Period17/08/1421/08/14

    Fingerprint

Keywords

  • Lattice-based cryptography
  • LWE
  • Traitor tracing

Cite this

Ling, S., Phan, D. H., Stehlé, D., & Steinfeld, R. (2014). Hardness of k-LWE and applications in traitor tracing. In J. A. Garay, & R. Gennaro (Eds.), Advances in Cryptology - CRYPTO 2014: 34th Annual Cryptology Conference, Proceedings (PART 1 ed., Vol. 8616 LNCS, pp. 315-334). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8616 LNCS, No. PART 1). Heidelberg: Springer, Springer Nature. https://doi.org/10.1007/978-3-662-44371-2_18