Lattices.io — Mathematical Lattices & 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.

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} ∣ b_{2} ∣ \dots ∣ b_{n}]$ , and the lattice is:

Λ (B) = {B x ∣ x \in Z^{n}}

Figure 1.1 — 2D Lattice Λ = { x₁b₁ + x₂b₂ | x₁, x₂ ∈ ℤ }

Vector b₁

Vector b₂

Origin

shaded region = fundamental domain

Loading 3D geometry...

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 R^{n \times n}$ . The lattice is:

Λ (B) = {B x ∣ x \in Z^{n}}

The symbol $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 impossible to answer efficiently, even with a quantum computer.

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 work on lattice problems. Lattice cryptography is therefore considered "post-quantum secure" — safe even in a world with powerful quantum computers.

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.