wp-plugin-hostgator domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/celebrated-cryptography-algorithm-gets-an-upgrade-20231214\/#comments<\/a><\/br> In our increasingly digital lives, security depends on cryptography. Send a private message or pay a bill online, and you\u2019re relying on algorithms designed to keep your data secret. Naturally, some people want to uncover those secrets \u2014 so researchers work to test the strength of these systems to make sure they won\u2019t crumble at the hands of a clever attacker.<\/p>\n One important tool in this work is the LLL algorithm, named after the researchers who published it<\/a> in 1982 \u2014 Arjen Lenstra, Hendrik Lenstra Jr. and L\u00e1szl\u00f3 Lov\u00e1sz. 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\u2019s talents stretch beyond cryptography: It\u2019s also a useful tool in advanced mathematical arenas such as computational number theory.<\/p>\n Over the years, researchers have honed variants of LLL to make the approach more practical \u2014 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<\/a> at the 2023 International Cryptology Conference<\/a>, widens the range of scenarios in which computer scientists and mathematicians can feasibly use LLL-like approaches.<\/p>\n \u201cIt was really exciting,\u201d said Chris Peikert<\/a>, 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. \u201cIt\u2019s always nice when a target that has been worked on for so long \u2026 shows that there\u2019s still surprises to be found.\u201d<\/p>\n LLL-type algorithms operate in the world of lattices: infinite collections of regularly spaced points. As one way of visualizing this, imagine you\u2019re 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 \u2014 say, a long parallelogram \u2014 to create a different lattice.<\/p>\n A lattice can be described using its \u201cbasis.\u201d 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\u2019s 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.<\/p>\n That pair of vectors isn\u2019t the lattice\u2019s 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 \u201cgood.\u201d An example of this is the pair of blue vectors in the figure below. Bases consisting of longer and less orthogonal vectors \u2014 like the red vectors \u2014 can be considered \u201cbad.\u201d<\/p>\n This is a job for LLL: Give it (or its brethren) a basis of a multi-dimensional lattice, and it\u2019ll spit out a better one. This process is known as lattice basis reduction.<\/p>\n What does this all have to do with cryptography? It turns out that the task of breaking a cryptographic system can, in some cases, be recast as another problem: finding a relatively short vector in a lattice. And sometimes, that vector can be plucked from the reduced basis generated by an LLL-style algorithm. This strategy has helped researchers topple systems that, on the surface, appear to have little to do with lattices.<\/p>\n In a theoretical sense, the original LLL algorithm runs quickly: The time it takes to run doesn\u2019t scale exponentially with the size of the input \u2014 that is, the dimension of the lattice and the size (in bits) of the numbers in the basis vectors. But it does increase as a polynomial function, and \u201cif you actually want to do it, polynomial time is not always so feasible,\u201d said L\u00e9o Ducas<\/a>, a cryptographer at the national research institute CWI in the Netherlands.<\/p>\n In practice, this means that the original LLL algorithm can\u2019t handle inputs that are too large. \u201cMathematicians and cryptographers wanted the ability to do more,\u201d said Keegan Ryan<\/a>, a doctoral student at the University of California, San Diego. Researchers worked to optimize LLL-style algorithms to accommodate bigger inputs, often achieving good performance. Still, some tasks have remained stubbornly out of reach.<\/p>\n The new paper, authored by Ryan and his adviser, Nadia Heninger<\/a>, combines multiple strategies to improve the efficiency of its LLL-style algorithm. For one thing, the technique uses a recursive structure that breaks the task down into smaller chunks. For another, the algorithm carefully manages the precision of the numbers involved, finding a balance between speed and a correct result. The new work makes it feasible for researchers to reduce the bases of lattices with thousands of dimensions.<\/p>\n Past work has followed a similar approach: A 2021 paper<\/a> also combines recursion and precision management to make quick work of large lattices, but it worked only for specific kinds of lattices, and not all the ones that are important in cryptography. The new algorithm behaves well on a much broader range. \u201cI\u2019m really happy someone did it,\u201d said Thomas Espitau<\/a>, a cryptography researcher at the company PQShield and an author of the 2021 version. His team\u2019s work offered a \u201cproof of concept,\u201d he said; the new result shows that \u201cyou can do very fast lattice reduction in a sound way.\u201d<\/p>\n The new technique has already started to prove useful. Aurel Page<\/a>, 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.<\/p>\n LLL-style algorithms can also play a role in research related to lattice-based cryptography systems designed to remain secure<\/a> even in a future with powerful quantum computers. They don\u2019t 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 \u201cbasic building block,\u201d said Wessel van Woerden<\/a>, 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.<\/p>\n Quanta\u00a0is conducting a series of surveys to better serve our audience. Take our <\/i>computer science reader survey<\/i><\/a> and you will be entered to win free<\/i>\u00a0Quanta\u00a0merchandise.<\/i><\/p>\n<\/div>\n <\/br><\/br><\/br><\/p>\n
\nCelebrated Cryptography Algorithm Gets an Upgrade<\/br>
\n2023-12-18 21:58:57<\/br><\/p>\n