In our increasingly digital lives, security depends on cryptography. Send a private message or pay a bill online, and you’re relying on algorithms designed to keep your data secret. Naturally, some people want to uncover those secrets — so researchers work to test the strength of these systems to make sure they won’t crumble at the hands of a clever attacker.
One important tool in this work is the LLL algorithm, named after the researchers who published it in 1982 — Arjen Lenstra, Hendrik Lenstra Jr. and László Lovász. LLL, along with its many descendants, can break cryptographic schemes in some cases; studying how they behave helps researchers design systems that are less vulnerable to attack. And the algorithm’s talents stretch beyond cryptography: It’s also a useful tool in advanced mathematical arenas such as computational number theory.
Over the years, researchers have honed variants of LLL to make the approach more practical — but only up to a point. Now, a pair of cryptographers have built a new LLL-style algorithm with a significant boost in efficiency. The new technique, which won the Best Paper award at the 2023 International Cryptology Conference, widens the range of scenarios in which computer scientists and mathematicians can feasibly use LLL-like approaches.
“It was really exciting,” said Chris Peikert, a cryptographer at the University of Michigan who was not involved in the paper. The tool has been the focus of study for decades, he said. “It’s always nice when a target that has been worked on for so long … shows that there’s still surprises to be found.”
LLL-type algorithms operate in the world of lattices: infinite collections of regularly spaced points. As one way of visualizing this, imagine you’re tiling a floor. You could cover it in square tiles, and the corners of those tiles would make up one lattice. Alternatively, you could choose a different tile shape — say, a long parallelogram — to create a different lattice.
A lattice can be described using its “basis.” This is a set of vectors (essentially, lists of numbers) that you can combine in different ways to get every point in the lattice. Let’s imagine a lattice with a basis consisting of two vectors: [3, 2] and [1, 4]. The lattice is just all the points you can reach by adding and subtracting copies of those vectors.
That pair of vectors isn’t the lattice’s only basis. Every lattice with at least two dimensions has infinitely many possible bases. But not all bases are created equal. A basis whose vectors are shorter and closer to right angles with one another is usually easier to work with and more useful for solving some computational problems, so researchers call those bases “good.” An example of this is the pair of blue vectors in the figure below. Bases consisting of longer and less orthogonal vectors — like the red vectors — can be considered “bad.”
This is a job for LLL: Give it (or its brethren) a basis of a multi-dimensional lattice, and it’ll spit out a better one. This process is known as lattice basis reduction.
What does this all have to do with cryptography? It turns out that the task of breaking a cryptographic system can, in some cases, be recast as another problem: finding a relatively short vector in a lattice. And sometimes, that vector can be plucked from the reduced basis generated by an LLL-style algorithm. This strategy has helped researchers topple systems that, on the surface, appear to have little to do with lattices.
In a theoretical sense, the original LLL algorithm runs quickly: The time it takes to run doesn’t scale exponentially with the size of the input — that is, the dimension of the lattice and the size (in bits) of the numbers in the basis vectors. But it does increase as a polynomial function, and “if you actually want to do it, polynomial time is not always so feasible,” said Léo Ducas, a cryptographer at the national research institute CWI in the Netherlands.
In practice, this means that the original LLL algorithm can’t handle inputs that are too large. “Mathematicians and cryptographers wanted the ability to do more,” said Keegan Ryan, a doctoral student at the University of California, San Diego. Researchers worked to optimize LLL-style algorithms to accommodate bigger inputs, often achieving good performance. Still, some tasks have remained stubbornly out of reach.
The new paper, authored by Ryan and his adviser, Nadia Heninger, combines multiple strategies to improve the efficiency of its LLL-style algorithm. For one thing, the technique uses a recursive structure that breaks the task down into smaller chunks. For another, the algorithm carefully manages the precision of the numbers involved, finding a balance between speed and a correct result. The new work makes it feasible for researchers to reduce the bases of lattices with thousands of dimensions.
Past work has followed a similar approach: A 2021 paper also combines recursion and precision management to make quick work of large lattices, but it worked only for specific kinds of lattices, and not all the ones that are important in cryptography. The new algorithm behaves well on a much broader range. “I’m really happy someone did it,” said Thomas Espitau, a cryptography researcher at the company PQShield and an author of the 2021 version. His team’s work offered a “proof of concept,” he said; the new result shows that “you can do very fast lattice reduction in a sound way.”
The new technique has already started to prove useful. Aurel Page, a mathematician with the French national research institute Inria, said that he and his team have put an adaptation of the algorithm to work on some computational number theory tasks.
LLL-style algorithms can also play a role in research related to lattice-based cryptography systems designed to remain secure even in a future with powerful quantum computers. They don’t pose a threat to such systems, since taking them down requires finding shorter vectors than these algorithms can achieve. But the best attacks researchers know of use an LLL-style algorithm as a “basic building block,” said Wessel van Woerden, a cryptographer at the University of Bordeaux. In practical experiments to study these attacks, that building block can slow everything down. Using the new tool, researchers may be able to expand the range of experiments they can run on the attack algorithms, offering a clearer picture of how they perform.
