Advancing Cryptography with the Expanded LLL Algorithm

Saturday - December 16 2023, 15:08 UTC - 11 months ago

Cryptographers have built a new LLL-style algorithm that significantly boosts the efficiency of LLL algorithms. This widens the range of scenarios in which computer scientists and mathematicians can feasibly use LLL-like approaches and can be beneficial in helping break cryptographic systems by finding ways to reduce lattice bases quickly.

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.

"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." .

LLL-type algorithms operate in the world of lattices: infinite collections of regularly spaced points. As one way of visualizing this, imagine you’re tiling a floor. You could cover it in square tiles, and the corners of those tiles would make up one lattice. Alternatively, you could choose a different tile shape — say, a long parallelogram — to create a different lattice.

A lattice can be described using its "basis." This is a set of vectors (essentially, lists of numbers) that you can combine in different ways to get every point in the lattice. Let’s imagine a lattice with a basis consisting of two vectors: [3, 2] and [1, 4]. The lattice is just all the points you can reach by adding and subtracting copies of those vectors.

That pair of vectors isn’t the lattice’s only basis. Every lattice with at least two dimensions has infinitely many possible bases. But not all bases are created equal. A basis whose vectors are shorter and closer to right angles with one another is usually easier to work with and more useful for solving some computational problems, so researchers call those bases "good." An example of this is the pair of blue vectors in the figure below. Bases consisting of longer and less orthogonal vectors — like the red vectors — can be considered "bad." .

This is a job for LLL: Give it (or its brethren) a basis of a multi-dimensional lattice, and it’ll spit out a better one. This process is known as lattice basis reduction.

What does this all have to do with cryptography? It turns out that the task of breaking a cryptographic system — deriving the secret key from the public information it’s based on — can often be translated into a lattice problem. This means that if you can find a way to reduce lattice bases quickly, you can open up some previously unviable cryptographic targets.