A Decade of Lattice Cryptography

Chris Peikert

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: lattices survey short integer solution learning 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: 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}
}