Learning With Errors: The Hard Problem
Understand the LWE and SIS problems, their hardness assumptions, and why they resist quantum attacks.
The LWE Problem Defined
The Learning With Errors (LWE) problem was introduced by Oded Regev in 2005 as a foundation for post-quantum cryptography. Given a random matrix A over Z_q and a vector b = As + e, the goal is to find the secret vector s. The vector e is a small error drawn from a discrete Gaussian distribution, making the problem computationally intractable.
LWE Matrix Structure
In the LWE problem, A is an m x n random matrix sampled uniformly over Z_q, where q is a prime modulus. The secret s is an n-dimensional vector, and e is a small error vector whose entries are drawn from a narrow Gaussian. Even knowing the structure of A does not help an adversary distinguish b from a uniformly random vector.
All lessons in this course
- Learning With Errors: The Hard Problem
- NTRU: History, Design, and Security
- Ring-LWE and Module Lattices
- Security Proofs and Reductions in Lattice Schemes