Cryptology ePrint Archive: Report 2015/939

A Decade of Lattice Cryptography

Chris Peikert

Abstract: Lattice-based cryptography is the use of conjectured hard problems on point lattices in $\R^{n}$ as the foundation for secure cryptographic constructions. Attractive features of lattice cryptography include: apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under 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 short integer solution (SIS) and 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 26 Sep 2015

Contact author: cpeikert at alum mit edu

Available format(s): PDF | BibTeX Citation

Version: 20150928:195131 (All versions of this report)

Short URL: ia.cr/2015/939

Discussion forum: Show discussion | Start new discussion