Lattices: the math behind post-quantum cryptography.

Imagine a perfectly regular grid of dots stretching infinitely in every direction — like graph paper, but in any number of dimensions. That grid is a lattice. Every dot is a lattice point, and to get from one dot to any other, you always move in whole-number steps along fixed directions. No fractions, no halfway positions — only exact integer steps.

A note on the word: in order theory, a lattice is also a partially ordered set in which any two elements have a least upper bound and a greatest lower bound. That is a different object. This site is about point lattices, the grids of points used in number theory and cryptography.

Those fixed directions are called basis vectors. On ordinary graph paper you have two of them: one pointing right, one pointing up. Step right twice and up once — you arrive at a lattice point. Step right three times and up negative one — another lattice point. Every single point on the grid can be reached this way. The lattice is the collection of all such reachable points. Pack the basis vectors as columns of a matrix $B = [b_1 \mid b_2 \mid \cdots \mid b_n]$, and the lattice is:

The 3D visualization above shows a lattice in three dimensions. Drag to rotate it. Notice how the points form a perfectly regular pattern — no randomness, no gaps that break the pattern. The three colored arrows are the basis vectors: the entire infinite lattice is built by taking integer combinations of just those three directions.

The Formal Definition

Once you have the intuition, the mathematical definition is just a precise restatement of it. We pick $n$ directions (basis vectors), and the lattice is everything you can reach with integer steps along those directions.

Definition 1 — Lattice

Choose $n$ vectors $b_1, \dots, b_n$ that all point in genuinely different directions (formally: they are linearly independent). Pack them as columns of a basis matrix $B \in \mathbb{R}^{n \times n}$. The lattice is:

The symbol $\mathbb{Z}$ means “the integers” — the whole numbers ..., −2, −1, 0, 1, 2, ...

Why Lattices Matter

Lattices have been studied for over two centuries — by Gauss, Minkowski, and others — in the context of number theory. But in the last 30 years they have become central to cryptography, for a remarkable reason: certain questions about lattices are extremely easy to ask but appear to be hard to answer efficiently. No efficient classical or quantum algorithm is known for the relevant problems at suitable parameters.

The simplest such question is: what is the shortest nonzero vector in this lattice? If I give you a complicated, skewed set of basis vectors, finding that shortest vector is believed to be computationally infeasible when the dimension $n$ is large (say, 512 or 1024). This hardness is what we build cryptography on top of.

Why they resist quantum computers

Most encryption used today — RSA, elliptic curve cryptography — will be broken the day a large enough quantum computer exists. The quantum algorithm that does this (Shor’s algorithm) does not solve the lattice problems used by current post-quantum schemes. No efficient quantum attack is known for those problems, which is why lattice cryptography is considered quantum resistant. This is a security assessment, not a proof that future attacks are impossible.

Computing on encrypted data

Lattices also enable Fully Homomorphic Encryption (FHE) — a way to run computations on data while it is still encrypted. A cloud server can add, multiply, and process your private numbers without ever seeing what they are. The mathematical structure that makes this possible is the lattice.

Already in your browser

Since August 2024, NIST has standardized the first post-quantum algorithms. The primary standard, ML-KEM (Kyber), is based on lattices and is already being deployed in Chrome, Cloudflare, and AWS to protect TLS connections. If you use the internet, you are already relying on lattice mathematics.