The original version of this story appeared in Quanta Magazine.
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.
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.
The tool has been the focus of study for decades, he said.
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.
You could choose a different tile shape-say, a long parallelogram-to create a different 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.
This Cyber News was published on www.wired.com. Publication date: Sun, 11 Feb 2024 13:43:04 +0000