Lattice-Based Cryptography

If you want to package a message so that only the recipient can read it, you need a computational problem that is practically unsolvable for outsiders. Lattice-based cryptography uses lattices for this: regular point patterns in space, similar to the corners of an infinitely large grid of squares or a crystal. Such lattices can be spanned not only flat on paper, but also in spaces with hundreds or thousands of dimensions. And there, a question that sounds harmless becomes extremely hard to answer: which lattice point lies closest to an arbitrarily given point? This difficulty is the core of the methods. They are also called lattice-based methods and belong to cryptography, the science of encryption.

Insurance against the quantum computer

Almost everything encrypted on the internet today rests on two old computational problems. One is factoring a very large number into its prime factors. The other is closely related and is called the discrete logarithm. Ordinary computers reliably fail at these. A sufficiently large quantum computer, however, could solve both problems in a manageable amount of time, using a method known since 1994, devised by Peter Shor.

For lattice problems, no such quantum trick is known to this day. That is why lattice-based cryptography is counted among post-quantum cryptography, i.e. the methods that are meant to hold up even after powerful quantum computers are built. The US agency NIST announced its first recommendations in 2022 after a multi-year competition. The most important of these, now called Kyber and Dilithium, are lattice-based.

The transition is more urgent than it sounds. An attacker can intercept encrypted data today, store it, and only decrypt it in ten or twenty years. Experts call this “harvest now, decrypt later”, meaning collect first, crack later. For medical records, banking data, or state secrets, this is a real problem.

Noise as a shield

Most lattice methods rest on a problem called “Learning with Errors”. Imagine a large system of equations, like the ones you know from school, only with thousands of unknowns. Without disturbance, it would be easy to solve. During encryption, however, a small, random error is added to each line. This deliberate noise makes the system practically unsolvable as long as you don’t know the secret key.

The secret key is a particularly convenient description of the lattice, made up of short and orderly direction vectors. Whoever possesses it finds the nearest lattice point instantly and can compute the noise back out. The public key describes the same lattice, but with directions chosen to be long and skewed. This lets anyone encrypt, but no one can find their way back. It’s the difference between a city map with street names and a list of arbitrarily scrambled directions.

A common misconception is that lattice methods are provably secure. What is actually proven is only a connection: whoever breaks the method could also solve the general lattice problem. That this problem is truly hard remains a well-tested assumption. In practice, this results in larger keys than with the old methods, often several kilobytes instead of a few hundred bytes. In return, the computation itself is fast, since it mostly involves addition and multiplication.

Kyber is already in your browser

The transition is already underway, mostly invisibly. Google Chrome and Firefox establish a connection when you open a website that combines Kyber with a classical method. Apple introduced a lattice-based key exchange for iMessage in 2024, and Signal did the same. Old and new are deliberately combined: if a weakness is found in one of the two methods, the other continues to provide protection.

In business news, you’ll encounter this topic under buzzwords like post-quantum migration or crypto agility. Banks, cloud providers, and chip manufacturers estimate the effort will take years, because encryption is built firmly into countless devices. Authorities are setting deadlines: the US wants critical systems converted by around 2035. For companies, this creates a market for consulting, testing tools, and new hardware.

Important for clarity: lattice-based cryptography is not a quantum technology. It runs on completely normal computers and smartphones. It is often confused with quantum cryptography, which uses light particles over fiber optics and requires special devices. Lattice-based methods are the practical path, while quantum key distribution is more of a niche product.