A Decade of Lattice Cryptography

2016/03/24 by Chris Peikert · 2 citations
Computer Science · Mathematics · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Privacy-Preserving Technologies in Data #Lattice-based cryptography #Learning with errors #Cryptography #Computer science #Post-quantum cryptography #Quantum cryptography #Lattice problem #Lattice (music) #Theoretical computer science #Mathematics #Encryption #Public-key cryptography #Quantum #Algorithm #Computer security #Quantum information #Physics #Quantum mechanics

paper · doi:10.1561/0400000074

openalex publication_date 2016/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/21

Abstract

Lattice-based cryptography is the use of conjectured hard problems on point lattices in ℝn 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.

Citations

• SWIFFT: A Modest Proposal for FFT Hashing
• Worst-case to average-case reductions for module lattices
• A hierarchy of polynomial time lattice basis reduction algorithms
• On lattices, learning with errors, random linear codes, and cryptography
• A Pseudorandom Generator from any One-way Function
• Identity-Based Encryption from the Weil Pairing
• The Learning with Errors Problem (Invited Survey)
• Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions
• Factoring polynomials with rational coefficients
• Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
• New directions in cryptography

Cited by

• Publicly Verifiable Secret Sharing: Generic Constructions and Lattice-Based Instantiations in the Standard Model
• Computational hardness assumption [wikipedia]

Related

• Some Mathematical Problems Behind Lattice-Based Cryptography
• A Tutorial Introduction to Lattice-based Cryptography and Homomorphic Encryption
• New Lattice Based Cryptographic Constructions
• On lattices, learning with errors, random linear codes, and cryptography
• Generating cryptographically-strong random lattice bases and recognizing rotations of ℤⁿ