Mathematics
Lattice-based cryptography and post-quantum security
Quick fact
In 2024, NIST selected lattice-based schemes (CRYSTALS-Kyber and CRYSTALS-Dilithium) as the first post-quantum standards, because no known quantum algorithm can efficiently solve the underlying lattice problems—unlike the factoring and discrete log problems that secure our current internet.
Why this is interesting
Your bank, your messages, your medical records—all are protected by math that a quantum computer could one day crack. What kind of math could replace it and keep the internet safe?
Read the full explanation
Understanding Lattice-based cryptography and post-quantum security
Imagine a lattice as a jungle gym that repeats infinitely in every direction. Just as a jungle gym is an array of intersecting bars, a lattice is an infinite set of points formed by taking all integer combinations of a few base vectors. For example, in 2D, the vectors (1,0) and (0,1) generate the integer grid. In high dimensions, these points form a sprawling structure. Lattice-based cryptography uses two core problems. The Shortest Vector Problem (SVP): find the shortest non-zero vector in the lattice (the shortest bar in the jungle gym). The Closest Vector Problem (CVP): given a random point in space, find the lattice point closest to it. In low dimensions, you might solve these by eye, but in hundreds of dimensions, they become incredibly hard. Why are they hard? The key is that you can describe a lattice to someone, but finding these special vectors is like searching a haystack in a thousand dimensions without knowing if you're getting warmer. There's no algorithm—classical or quantum—that can solve them efficiently, even though checking a candidate solution is easy. This asymmetry—easy to verify but hard to solve—is the foundation of cryptographic security. Your intuition for 'hard' is built on small dimensions. In 2D, you can see the lattice and run algorithms to find the shortest vector. But as dimensions grow exponentially, the search space explodes. This is what makes lattices useful: they provide extreme complexity with simple rules.
A deeper explanation
The magic of lattice-based cryptography lies in a surprising mathematical leap: we can connect the worst-case difficulty of lattice problems to the average-case difficulty of a new problem, called Learning With Errors (LWE). LWE asks you to solve a system of linear equations like y = Ax + s + e, where A is a random matrix, s is the secret, and e is a small error term (noise). Without the noise, linear algebra solves this instantly—Gaussian elimination works. With the noise, everything changes. The error breaks the linear structure, and the problem becomes hard. The remarkable theorem, proven by Oded Regev in 2005, states that solving LWE (on average) is as hard as solving worst-case lattice problems like SVP. This means a secure system built on LWE is built on the most difficult version of the lattice problem, not just some easy average instance. This worst-case to average-case hardness is what gives lattice-based cryptography its confidence. Moreover, these problems are believed to be quantum-hard; Shor's algorithm, which breaks RSA and ECC by solving their underlying mathematical shortcuts, does not work here because lattices offer no such shortcut. Lifetime and performance are also practical advantages. Lattice operations are simple matrix-vector multiplications with small integers, making them fast on standard hardware. This is why NIST's selection of lattice-based schemes—Kyber for encryption and Dilithium for signatures—is the key to moving the internet to post-quantum security. However, there are subtleties. Parameter selection is delicate: choose too small, and the problem becomes solvable; choose too large, and performance suffers. There are also ongoing attacks that exploit side-channels or implementation flaws. But the mathematical foundation remains solid: as of today, no known algorithm—quantum or classical—can crack these problems.