Paper 2011/501

Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller

Daniele Micciancio and Chris Peikert

Abstract

We give new methods for generating and using ``strong trapdoors'' in cryptographic lattices, which are simultaneously simple, efficient, easy to implement (even in parallel), and asymptotically optimal with very small hidden constants. Our methods involve a new kind of trapdoor, and include specialized algorithms for inverting $\lwe$, randomly sampling $\sis$ preimages, and securely delegating trapdoors. These tasks were previously the main bottleneck for a wide range of cryptographic schemes, and our techniques substantially improve upon the prior ones, both in terms of practical performance and quality of the produced outputs. Moreover, the simple structure of the new trapdoor and associated algorithms can be exposed in applications, leading to further simplifications and efficiency improvements. We exemplify the applicability of our methods with new digital signature schemes and CCA-secure encryption schemes, which have better efficiency and security than the previously known lattice-based constructions.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
lattice cryptographylattice trapdoors
Contact author(s)
cpeikert @ cc gatech edu
History
2011-09-18: received
Short URL
https://ia.cr/2011/501
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/501,
      author = {Daniele Micciancio and Chris Peikert},
      title = {Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller},
      howpublished = {Cryptology ePrint Archive, Paper 2011/501},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/501}},
      url = {https://eprint.iacr.org/2011/501}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.