Celebrated Cryptography Algorithm Gets an Upgrade
Arthur T Knackerbracket has processed the following story:
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 Laszlo Lovasz. 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."
[...] 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.
The new paper mentioned:
Ryan, K., Heninger, N. (2023). Fast Practical Lattice Reduction Through Iterated Compression. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology - CRYPTO 2023. CRYPTO 2023. Lecture Notes in Computer Science, vol 14083. Springer, Cham. https://doi.org/10.1007/978-3-031-38548-3_1
Read more of this story at SoylentNews.