Learning With Errors (LWE)
The mathematical foundation of PQC
Adding Intentional Noise
In 2005, Oded Regev proposed taking easily solvable equations and corrupting each with tiny random errors. The errors are minuscule — like adding random pennies to restaurant bills — but compound into mathematical chaos. Finding the secret variables requires simultaneously guessing every error — a problem proven NP-Hard.
The File Size Crisis
Pure required matrices of 1,000 × 1,000 numbers — one million numbers per public key, several megabytes in size. Far too large for the modern internet.
MLWE: Polynomial Compression
groups numbers into structured polynomial blocks of 256 values each. Because of their structure, only a few blocks need to be transmitted. Public keys shrink from megabytes to ~1,100 bytes — fitting in a standard internet packet.
The modular design enables 's scalability tiers: ML-KEM-512 (2×2 grid, equivalent), ML-KEM-768 (3×3, AES-192), and ML-KEM-1024 (4×4, ). Increasing security means adding one more module — no code rewrites.
MLWE is the mathematical engine powering both ML-KEM (key exchange) and ML-DSA (signatures) — the two primary NIST PQC standards.
Key Takeaways
- LWE adds intentional random noise to solvable equations, making them NP-Hard even for quantum computers
- Pure LWE had a fatal flaw: million-number matrices made keys several megabytes
- MLWE solved the size problem by grouping numbers into polynomial modules — keys shrink to ~1,100 bytes