Foundations and Trends® in Theoretical Computer Science > Vol 10 > Issue 4

A Decade of Lattice Cryptography

By Chris Peikert, University of Michigan, USA, cpeikert@gmail.com

 
Suggested Citation
Chris Peikert (2016), "A Decade of Lattice Cryptography", Foundations and TrendsĀ® in Theoretical Computer Science: Vol. 10: No. 4, pp 283-424. http://dx.doi.org/10.1561/0400000074

Publication Date: 24 Mar 2016
© 2016 C. Peikert
 
Subjects
Cryptography and information security,  Computational complexity,  Randomness in computation,  Quantum computation
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction 
2. Background 
3. Early Results 
4. Modern Foundations 
5. Essential Cryptographic Constructions 
6. Advanced Constructions 
7. Open Questions 
Acknowledgments 
References 

Abstract

Lattice-based cryptography is the use of conjectured hard problems on point lattices in Rn as the foundation for secure cryptographic systems. 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.

DOI:10.1561/0400000074
ISBN: 978-1-68083-112-2
156 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-68083-113-9
156 pp. $130.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Background
3. Early Results
4. Modern Foundations
5. Essential Cryptographic Constructions
6. Advanced Constructions
7. Open Questions
Acknowledgments
References

A Decade of Lattice Cryptography

Lattice-based cryptography is the use of conjectured hard problems on point lattices in Rn as the foundation for secure cryptographic systems. 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 monograph 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.

 
TCS-074