Lattice-Based Cryptography
Ajtai (1996) and Regev (2005) found a way to build encryption on the difficulty of finding the shortest arrow in a huge multi-dimensional grid of points, which, unlike RSA, no quantum attack is known to break.
Open in the interactive tree →In 1996 Miklós Ajtai built the first lattice-based construction whose security rests on well-studied lattice problems. In 2005 Oded Regev introduced learning with errors (LWE), which hides a secret by adding small random noise; he showed it is as hard as several worst-case lattice problems and won the 2018 Gödel Prize. Shor's algorithm would break RSA and elliptic curves on a large quantum computer, but lattice problems appear to resist both normal and quantum computers. On 13 August 2024 NIST published its first post-quantum standards, including ML-KEM (based on CRYSTALS-Kyber) for key exchange and ML-DSA (based on CRYSTALS-Dilithium) for signatures, both lattice-based.
Prerequisites
- Linear Algebra & Matrices1858A lattice is a regular grid of points built from vectors.
- Complexity Theory & NP1971Security rests on problems believed to be hard even in the worst case.
- Public-Key Cryptography1976Lattice schemes do the job of RSA and Diffie-Hellman.
Unlocks
- Post-Quantum Cryptography2024ML-KEM and ML-DSA, the new standards, are lattice-based schemes.