Cryptology ePrint Archive: Report 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.

Category / Keywords: lattices, survey, short integer solution, learning with errors

Date: received 25 Sep 2015, last revised 17 Feb 2016

Contact author: cpeikert at alum mit edu

Available format(s): PDF | BibTeX Citation

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

Version: 20160218:034642 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]