Paper 2015/939

A Decade of Lattice Cryptography

Chris Peikert

Abstract

\emph{Lattice-based cryptography} is the use of conjectured hard problems on point lattices in~$\R^{n}$ as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to \emph{quantum} attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under \emph{worst-case} intractability assumptions, and solutions to long-standing open problems in cryptography. This work surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational \emph{short integer solution}~(SIS) and \emph{learning with errors}~(LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.

Note: Added details to some proof outlines; minor typographical edits.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
latticessurveyshort integer solutionlearning with errors
Contact author(s)
cpeikert @ alum mit edu
History
2016-02-18: revised
2015-09-28: received
See all versions
Short URL
https://ia.cr/2015/939
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/939,
      author = {Chris Peikert},
      title = {A Decade of Lattice Cryptography},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/939},
      year = {2015},
      url = {https://eprint.iacr.org/2015/939}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.