A famous cryptography-breaking algorithm just got an upgrade


This is a task for LLL: give it (or its brothers) a multidimensional lattice basis, and it will generate a better lattice. This process is known as lattice basis reduction.

What does all this have to do with cryptography? It turns out that the task of breaking cryptographic systems can, in some cases, be recast as another problem: finding a relatively small vector in a lattice. And sometimes, that vector can be extracted from a reduced basis generated by an LLL-style algorithm. This strategy has helped researchers uncover systems that superficially have nothing to do with lattices.

In a theoretical sense, the basic LLL algorithm runs fast: the time it takes to run does not increase exponentially with the size of the input – that is, the dimension of the lattice and the size of the numbers (in bits) in the basis vectors. But it grows as a polynomial function, and “if you really want to do it, polynomial time is not always that feasible,” said cryptographer Leo Dukas of the national research institute CWI in the Netherlands.


In practice, this means that the original LLL algorithm cannot handle very large inputs. “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 adapt LLL-style algorithms to accommodate larger inputs, often achieving good performance. Yet, some tasks remain stubbornly out of reach.

The new paper, written by Ryan and his advisor, Nadia Henninger, combines several strategies to improve the efficiency of their LLL-style algorithms. For one thing, the technique uses a recursive structure that breaks the task into smaller pieces. For another, the algorithm carefully manages the precision of the numbers involved, finding a balance between speed and the correct result. The new work makes it possible for researchers to reduce lattice bases to thousands of dimensions.

Previous work has followed a similar approach: The 2021 paper also combines recursion and precision management to make quick work of large lattices, but it only works for specific types of lattices, and not all of them. Which are important in cryptography. The new algorithm behaves well over a much wider range. “I'm really glad someone did this,” said Thomas Espitou, a cryptography researcher at the company PQShield and author of the 2021 edition. His team's work, he said, offered a “proof of concept”; The new results show that “you can make lattice reductions very fast in a good way.”

New technology has started proving useful. Mathematician Aurel Page of the French national research institute Inria said he and his team have put an adaptation of the algorithm to work on some computational number theory tasks.

LLL-style algorithms may also play a role in research related to lattice-based cryptography systems designed to be secure even in a future with powerful quantum computers. They do not pose a threat to such systems, because removing them requires finding vectors smaller than these algorithms. But the best attack researchers know how to use LLL-style algorithms as “fundamental building blocks,” said cryptographer Wessel van Woerden of the University of Bordeaux. In practical experiments to study these attacks, that building block can slow everything down. Using the new tools, researchers may be able to expand the range of experiments that can be run on attack algorithms, offering a clearer picture of how they perform.

original story Reprinted with permission quanta magazine, An editorially independent publication of Simons Foundation Its mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.