A Celebrated Cryptography-Breaking Algorithm Just Got an Upgrade

Here’s a job for LLL: give it (or its brethren) the basis of a multidimensional lattice, and it’ll spit out a better one. This process is known as spurious base reduction.

What does all this have to do with cryptography? This suggests 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, this vector can be extracted from a reduced basis generated by an LLL-style algorithm. This strategy has helped researchers collapse systems that, on the surface, have little to do with lattices.

Theoretically, the original LLL algorithm runs fast: the time it takes to run it does not scale 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 vector—but It grows as a polynomial function, and “if you really want to do it, polynomial time isn’t always that feasible,” said Leo Doukas, a cryptographer at the national research institute CWI in the Netherlands.

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

The new paper, written by Ryan and his advisor, Nadia Hangercombines several strategies to improve the performance of its LLL-style algorithm. For one thing, the technique uses a repetitive structure that breaks the task into smaller parts. For another, the algorithm carefully manages the accuracy of the numbers involved, finding a balance between speed and accurate results. The new work makes it possible for researchers to reduce lattice bases with thousands of dimensions.

Past work has followed a similar approach: A 2021 Paper It also combines iteration and precision management to make large lattices work faster, but it only works for certain types of lattices, not all lattices that are important in cryptography. The new algorithm behaves well over a much wider range. “I’m really glad somebody did it,” said Thomas Espritau, is a cryptography researcher at the company PQShield and the author of the 2021 version. His team’s work produced a “proof of concept.” “You can reduce lattices very quickly in an acoustic way,” the new result shows.

The new technique is already proving effective. Oriel PageA mathematician at the French national research institute Enria said he and his team have adapted the algorithm to work on some computational number theory tasks.

LLL-style algorithms can also play a role in research related to lattice-based cryptographic systems. be safe Even in the future with powerful quantum computers. They do not pose a threat to such systems, as they require fewer vector searches than these algorithms to take down. But the best attack researchers know how to use LLL-style algorithms as “basic building blocks”. Wessel van WoerdenA 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 attack algorithms, providing a clearer picture of how they perform.

The original story Reprinted with permission. Quanta Magazine, Editorially independent publication of Simon Foundation Its mission is to enhance the public’s understanding of science by covering research developments and trends in the mathematical and physical and life sciences.