This is LLL’s job. If you give LLL (or its siblings) the basis for a multidimensional lattice, it will spit out a better lattice. This process is known as lattice basis reduction.
What does this all have to do with cryptography? It turns out that the task of deciphering cryptographic systems can sometimes be rephrased as another problem: finding relatively short vectors in a lattice . And in some cases, you can extract that vector from a reduced basis produced by an LLL-style algorithm. This strategy helped researchers break through a system that, on the surface, appeared to have little to do with lattices.
In a theoretical sense, the original LLL algorithm runs fast. The execution time does not increase exponentially with the size of the input, i.e. the dimension of the lattice and the size (in bits) of the numbers within it. basis vector. But it increases as a polynomial function, and “polynomial time isn’t necessarily feasible if you actually want to do it,” said Leo Ducasse, a cryptologist at the Dutch national research institute CWI. said.
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.” Keegan Ryan, a doctoral student at the University of California, San Diego. Researchers have worked to optimize LLL-style algorithms to accommodate larger inputs, often achieving good performance. Still, some challenges remain out of reach.
A new paper written by Ryan and his advisors Nadia Henningercombines multiple strategies to improve the efficiency of LLL-style algorithms. First, the technique uses a recursive structure that divides tasks into smaller chunks. The other is to carefully manage the precision of the numbers that the algorithm involves, finding a balance between speed and correct results. New research allows researchers to shrink the base of lattices by thousands of dimensions.
Previous studies followed a similar approach. 2021 Papers Also, while recursion and quality control can be combined to quickly process large lattices, it only worked for certain types of lattices, not all lattices that are important in cryptography. The new algorithm works better over a wider range. “I’m really glad someone did it,” he said. Thomas Espitau, a cryptographic researcher at PQShield and author of the 2021 edition. His team’s work provided “proof of concept,” he said. The new results show that “lattice reduction can be performed very quickly in a sane manner.”
This new technology is already beginning to prove useful. Aurel PageThe mathematician at France’s national research institute Inria said he and his team adapted the algorithm to tackle several computational number theory tasks.
LLL-style algorithms can also play a role in research related to lattice-based cryptographic systems designed to: stay safe Even in a future where powerful quantum computers have appeared. They are not a threat to such systems because bringing them down requires finding shorter vectors than these algorithms can achieve. But the best attacks known to researchers use LLL-style algorithms as “a fundamental building block,” he said. Wessel van Woerden, a cryptologist at the University of Bordeaux. In real experiments studying these attacks, that component can slow everything down. New tools could allow researchers to expand the range of experiments they can perform on attack algorithms and provide a clearer picture of how attack algorithms perform.
original story Reprinted with permission from Quanta Magazine, Editorially independent publication simmons foundation Its mission is to enhance the public’s understanding of science by covering research developments and trends in mathematics, physical sciences, and life sciences.
