[MP12] Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller

Authors: Daniele Micciancio, Chris Peikert | Venue: EUROCRYPT 2012 | Source

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 notion of trapdoor in terms of a basis for a special lattice, and new algorithms for generating such trapdoors and for using them to sample short preimages of targets. These are the central operations required by many lattice-based cryptographic schemes, and our methods represent a substantial improvement in practical efficiency over prior work. We also show that the new trapdoor generation algorithm can be used as a generic converter that allows any cryptographic scheme proven secure relative to the old trapping mechanism to be instantiated using the new one.

BibTeX

Copy

@Inproceedings{EC:MicPei12,
  author = {Daniele Micciancio and Chris Peikert},
  title = {Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller},
  pages = {700--718},
  editor = {David Pointcheval and Thomas Johansson},
  booktitle = {Advances in Cryptology -- {EUROCRYPT}~2012},
  volume = {7237},
  series = {Lecture Notes in Computer Science},
  address = {Cambridge, UK},
  month = {apr~15--19},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2012},
  doi = {10.1007/978-3-642-29011-4_41},
}