The innovation promises qualitative changes in the approach to data security.
In the era of digitalization of our lives, security largely depends on cryptography: from sending private messages to paying bills online. Researchers are working tirelessly to test the reliability of cryptographic systems to ensure that they are resistant to attacks.
An important tool in this work is the LLL algorithm, named after its creators Arjen Lenstra, Hendrik Lenstra Jr. and Laszlo Lovas, introduced and published back in 1982. This algorithm and its derivatives can in some cases crack cryptographic schemes, which helps developers create more secure systems. The LLL algorithm is also used in advanced mathematical fields, such as computational number theory.
At a recent international conference on cryptology, researchers presented a new LLL-style algorithm that significantly improves the efficiency and expands the scope of such methods.
LLL algorithms work with lattices — infinite collections of points located at regular intervals. They can be described using a "basis" - a set of vectors that can be combined to obtain any point in the lattice. The process of reducing the lattice basis makes it possible in some cases to crack cryptographic systems, reformulating the hacking problem as a search for a relatively short vector in the lattice.
The original LLL algorithm cannot handle too large input data, and this is the reason for conducting research in this direction.
The new work, authored by Ryan Keegan and his research advisor, Nadia Heninger, combines several strategies to improve the efficiency of its LLL-style algorithm. First, the method uses a recursive structure that breaks the problem down into smaller parts. Second, the algorithm carefully manages the accuracy of the numbers used, finding a balance between speed and the correct result. The new work allows researchers to reduce the bases of lattices with thousands of dimensions.
Such algorithms play an important role in the research of lattice-based cryptosystems, which are designed to provide security even in the future with the existence of powerful quantum computers. The new tool can expand the ability of experiments to study attacks on these systems, providing a clearer picture of their effectiveness.
In the era of digitalization of our lives, security largely depends on cryptography: from sending private messages to paying bills online. Researchers are working tirelessly to test the reliability of cryptographic systems to ensure that they are resistant to attacks.
An important tool in this work is the LLL algorithm, named after its creators Arjen Lenstra, Hendrik Lenstra Jr. and Laszlo Lovas, introduced and published back in 1982. This algorithm and its derivatives can in some cases crack cryptographic schemes, which helps developers create more secure systems. The LLL algorithm is also used in advanced mathematical fields, such as computational number theory.
At a recent international conference on cryptology, researchers presented a new LLL-style algorithm that significantly improves the efficiency and expands the scope of such methods.
LLL algorithms work with lattices — infinite collections of points located at regular intervals. They can be described using a "basis" - a set of vectors that can be combined to obtain any point in the lattice. The process of reducing the lattice basis makes it possible in some cases to crack cryptographic systems, reformulating the hacking problem as a search for a relatively short vector in the lattice.
The original LLL algorithm cannot handle too large input data, and this is the reason for conducting research in this direction.
The new work, authored by Ryan Keegan and his research advisor, Nadia Heninger, combines several strategies to improve the efficiency of its LLL-style algorithm. First, the method uses a recursive structure that breaks the problem down into smaller parts. Second, the algorithm carefully manages the accuracy of the numbers used, finding a balance between speed and the correct result. The new work allows researchers to reduce the bases of lattices with thousands of dimensions.
Such algorithms play an important role in the research of lattice-based cryptosystems, which are designed to provide security even in the future with the existence of powerful quantum computers. The new tool can expand the ability of experiments to study attacks on these systems, providing a clearer picture of their effectiveness.
