A Celebrated Cryptography-Breaking Algorithm Just Got an Upgrade
In our increasingly digital lives, security depends on cryptography. Send a private message or pay a bill online, and you’re relying on algorithms designed to keep your data secret. Naturally, some people want to uncover those secrets—so researchers work to test the strength of these systems to make sure they won’t crumble at the hands of a clever attacker.
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 László Lovász. 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.
