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
-
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},
note = {\url{https://eprint.iacr.org/2015/939}},
url = {https://eprint.iacr.org/2015/939}
}
