Lattice-based cryptography

When you send data over the internet, it gets encrypted: the text is turned into a jumble of numbers that only the recipient can reverse. For this to be secure, you need a computational problem that is easy to solve in one direction and practically impossible in reverse. Lattice-based cryptography uses point lattices for this purpose. A lattice is a regular pattern of points in space, similar to the intersections on graph paper, except not in two directions but in hundreds of directions at once. The hard problem is this: given an arbitrary point in space, find the nearest lattice point. In a few directions this is easy, but in hundreds of directions no one knows a fast method. It is precisely this gap between easy and impossible that makes encryption possible.

The reason for the worldwide transition

Almost all methods used on the internet today rely on two problems: factoring very large numbers into their prime factors, and a similarly structured problem involving powers. Both are hopelessly difficult for ordinary computers. For a quantum computer, meaning a machine based on quantum-physical effects rather than ordinary switches, they are not. In 1994, the mathematician Peter Shor showed a computational method that quickly solves both problems on such a machine.

Such quantum computers so far exist only in small, error-prone versions. Nevertheless, the danger is real, for an unpleasant reason. An attacker can record encrypted data traffic today and store it for decades. As soon as a suitable machine exists, they can decrypt the archive retroactively. Experts call this “harvest now, decrypt later.” For medical records, state secrets, or bank data, this is a serious problem.

With lattices, no one has yet found a quantum computational method that significantly speeds up the problem. The US agency NIST therefore declared several methods to be standards in 2024, following a years-long open competition. The most important of these, Kyber for key exchange and Dilithium for digital signatures, are lattice-based.

Noise as a shield

The central trick is called “Learning with Errors.” You set up many simple equations, of the kind: three times the first secret number plus five times the second yields a certain value. Given enough such equations, any student could work out the secret numbers. Now a small random error, a bit of noise, is deliberately added to each result.

This breaks the usual method of solving. Each computational step magnifies the error, and in the end only nonsense remains. Anyone who knows the secret numbers, however, can round away the noise, because they know roughly where the result must lie. The secret key, then, is the knowledge of which lattice directions are short and manageable. The public key describes the same lattice, but in distorted, long directions that are of no use to anyone.

In practice, calculations are not done with individual numbers but with polynomials, meaning expressions like x cubed plus two x. This allows for fast computational tricks and keeps the keys manageable. A Kyber key is roughly 800 to 1600 bytes in size. That is about twenty times more than with the old methods, but the computation time is often even shorter. Incidentally, a common misconception is that quantum physics is used here. These methods run on completely ordinary computers; they are merely designed to withstand quantum attacks.

Where Kyber and Dilithium are already running

You very likely use lattice-based cryptography every day without noticing. Google has built Kyber into the Chrome browser, Apple uses it to secure iMessage messages, and the messenger Signal uses it as well. This usually runs “hybrid”: old and new encryption are applied simultaneously. Should a weakness be found in the new method, the tried-and-tested method still provides protection.

In business news, these terms appear under the keyword post-quantum cryptography. Banks, data centers, and government agencies face expensive transition projects, because encryption is embedded in countless devices and programs. Germany’s BSI and US agencies name the early 2030s as the target date. Whoever manufactures chips or security software stands to profit, and corresponding companies are being closely watched on the stock market.

To draw a distinction: lattice-based methods are not the same as quantum cryptography. The latter sends individual light particles over fiber optic cable and requires special hardware. Lattice-based methods are pure software and can be distributed via update. This is precisely why they are the path the industry has chosen.