Learning With Errors

Regev's 2005 hard problem — solving noisy linear equations — that underpins nearly all standardized post-quantum cryptography.

Core Principles & Analysis

• Oded Regev proved solving random LWE instances is as hard as worst-case lattice problems — a rare average-case guarantee.
• Adding small random noise to linear equations turns trivial algebra into a conjecturally quantum-hard problem.
• The paper earned Regev the 2018 Gödel Prize as post-quantum migration began in earnest.

Specifications & Metrics

• TYPE: Hard problem
• YEAR: 2005