The Learning with Errors Problem (Invited Survey)

2010/06/01 by Oded Regev · 4 citations
Computer Science · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Cryptography and Residue Arithmetic #Computer science #Learning with errors #Cryptography #Theoretical computer science #Artificial intelligence #Computer security

paper · doi:10.1109/ccc.2010.26

openalex publication_date 2010/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04

Abstract

In this survey we describe the Learning with Errors (LWE) problem, discuss its properties, its hardness, and its cryptographic applications.

Citations

• SWIFFT: A Modest Proposal for FFT Hashing
• On lattices, learning with errors, random linear codes, and cryptography
• Public-key cryptosystems from the worst-case shortest vector problem
• Noise-tolerant learning, the parity problem, and the statistical query model
• On Ideal Lattices and Learning with Errors over Rings
• 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

Cited by

• A Decade of Lattice Cryptography
• EFFACT: A Highly Efficient Full-Stack FHE Acceleration Platform
• Publicly Verifiable Secret Sharing: Generic Constructions and Lattice-Based Instantiations in the Standard Model
• Computational hardness assumption [wikipedia]

Related

• Classical Hardness of Learning with Errors
• Ring Learning With Errors: A crossroads between postquantum cryptography, machine learning and number theory
• On the hardness of the Learning with Errors problem with a discrete reproducible error distribution
• Learning with Errors is easy with quantum samples
• Analogy between Learning With Error Problem and Ill-Posed Inverse Problems