A Celebrated Cryptography-Breaking Algorithm Just Got an Upgrade


That's LLL's job: give him (or his brothers) the basis of a multidimensional network, and he will create a better one. This process is known as network base reduction.

What does all this have to do with cryptography? It turns out that the task of cracking a cryptographic system can, in some cases, be transformed into another problem: finding a relatively short vector in a network. And sometimes this vector can be extracted from the reduced basis generated by an LLL style algorithm. This strategy has helped researchers overturn systems that, at first glance, appear to have little to do with networks.

From a theoretical point of view, the original LLL algorithm executes quickly: the time required for its execution does not scale exponentially with the size of the input, i.e. the dimension of the network and the size (in bits) of the numbers in the basis vectors. But it increases as a polynomial function, and “if you actually want to do it, polynomial time is not always that 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 cannot handle inputs that are too large. “Mathematicians and cryptographers wanted to be able to do more,” said Keegan Ryan, doctoral student at the University of California, San Diego. Researchers have worked to optimize LLL-like algorithms to accommodate larger inputs, often achieving good performance. Yet some tasks remain stubbornly out of reach.

The new document, written by Ryan and his advisor, Nadia Heninger, combines several strategies to improve the efficiency of its LLL-style algorithm. On the one hand, the technique uses a recursive structure that divides the task into smaller pieces. On the other hand, the algorithm carefully manages the precision of the digits involved, finding a balance between speed and correct result. The new work allows researchers to reduce network bases to thousands of dimensions.

Previous work has followed a similar approach: A paper 2021 also combines recursion and precision handling to speed up work on large networks, but it only worked for specific types of networks, and not for all those important in cryptography. The new algorithm performs well over a much wider range. “I'm really happy that someone did it,” said Thomas Espitau, a cryptography researcher at the company PQShield and author of the 2021 version. His team's work offered a “proof of concept,” he said; the new result shows that “you can do network reduction very quickly and in a healthy way.”

The new technique has already started to prove useful. Aurel Pagea mathematician at the French national research institute Inria, said he and his team implemented an adaptation of the algorithm to work on some number theory computational tasks.

LLL-type algorithms may also play a role in research related to network cryptography systems designed to stay safe even in a future with powerful quantum computers. They do not pose a threat to such systems, because removing them requires finding vectors shorter than those these algorithms can achieve. But the best attacks known to researchers use an LLL-like algorithm as a “building block,” said Wessel van Woerden, cryptographer at the University of Bordeaux. In practical experiments aimed at studying these attacks, this basic element can slow everything down. With this new tool, researchers may be able to expand the range of experiments they can run on attack algorithms, providing a clearer picture of their performance.


Original story reprinted with permission from Quanta Magazine, an editorially independent publication of Simons Foundation whose mission is to improve public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.



Source link

Scroll to Top