Lattice Theory

Draw all the crossing points of the lines on graph paper. What you get is a regular pattern of points: infinitely many points, always the same distance apart, extending in every direction. In mathematics, such a pattern is called a lattice. Lattice theory is the field that studies such patterns — not only in the plane, however, but also in space and in spaces with hundreds or thousands of dimensions that can no longer be visualized. It asks, for example, which lattice point lies closest to any given location. This seemingly harmless question is the reason why the field currently plays a major role in IT security.

The path to quantum-safe encryption

Almost all encryption on the internet today relies on two computational problems: factoring large numbers into their factors and a related problem involving powers. Both are considered practically unsolvable for ordinary computers if the numbers are large enough. The problem: this does not hold for quantum computers. A method from 1994, Shor’s algorithm, would quickly solve both problems on a sufficiently large quantum machine.

Such machines do not yet exist at a usable scale. Nevertheless, the danger is real, because attackers can intercept and store encrypted data today. It would then be decrypted in ten or twenty years. For state secrets, patient records, or bank data, this poses a serious risk.

Lattice problems look different. So far, no one knows a fast quantum algorithm for them. That is why the US agency NIST published the first official standards for quantum-safe encryption in 2024 — and the most important of them are based on lattices. One example is the ML-KEM method, formerly known as Kyber.

The shortest vector and why no one finds it

A lattice is described by a few basic directions, so-called basis vectors. All lattice points are generated by combining these directions an integer number of times. The crucial point: the same lattice can be described by very different basic directions. One basis can be short and orthogonal, another long and heavily skewed — the set of points remains identical.

With a short, tidy basis, two classic problems are easy. First: find the lattice point closest to the origin, but not the origin itself. Second: find, for any location in space, the nearest lattice point. With a skewed basis, both tasks become extremely hard in high dimensions. At a thousand dimensions, all known methods fail.

This is exactly what encryption methods build on. The public key roughly corresponds to the bad, skewed basis, the secret key to the good one. A message is encrypted by attaching it to a lattice point and then adding a bit of random noise. Whoever holds the good basis can calculate away the noise and arrive back at the correct point. Everyone else faces a search problem in a thousand dimensions.

Lattices in browsers, chats, and AI models

Lattice cryptography is no longer just theory. Google and Cloudflare have built quantum-safe key exchanges into their systems, Apple secures iMessage with it, and Signal uses a similar method. A current Chrome or Firefox browser already negotiates many connections using lattice-based methods. Users notice nothing except slightly larger data packets.

In business news, the topic appears under the keyword post-quantum cryptography. Banks, government agencies, and chip manufacturers will have to overhaul their systems in the coming years, which will cost billions and correspondingly generate a great many contracts.

A second area of application lies in AI. Homomorphic encryption allows computations to be performed on encrypted data without decrypting it first. A hospital could thus have patient data evaluated by an AI model without disclosing it. These methods, too, are based on lattices. They are currently still very slow, but are regarded as one of the most important research directions for privacy in AI.