Close Menu
Technology Mag

    Subscribe to Updates

    Get the latest creative news from FooBar about art, design and business.

    What's Hot

    Here’s everything you need to know about preordering the 2025 iPhone lineup

    September 9, 2025

    You can now preorder the Apple Watch SE 3, Series 11, and Ultra 3

    September 9, 2025

    Psychological Tricks Can Get AI to Break the Rules

    September 9, 2025
    Facebook X (Twitter) Instagram
    Subscribe
    Technology Mag
    Facebook X (Twitter) Instagram YouTube
    • Home
    • News
    • Business
    • Games
    • Gear
    • Reviews
    • Science
    • Security
    • Trending
    • Press Release
    Technology Mag
    Home » A Celebrated Cryptography-Breaking Algorithm Just Got an Upgrade
    Security

    A Celebrated Cryptography-Breaking Algorithm Just Got an Upgrade

    News RoomBy News RoomFebruary 12, 20244 Mins Read
    Facebook Twitter Pinterest LinkedIn Reddit WhatsApp Email

    This is a job for LLL: Give it (or its brethren) a basis of a multidimensional 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 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.

    In a theoretical sense, the original LLL algorithm runs quickly: The time it takes to run doesn’t scale exponentially with the size of the input—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 “if you actually want to do it, polynomial time is not always so feasible,” said Léo Ducas, a cryptographer at the national research institute CWI in the Netherlands.

    In practice, this means that the original LLL algorithm can’t handle inputs that are too large. “Mathematicians and cryptographers wanted the ability to do more,” said Keegan Ryan, 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.

    The new paper, authored by Ryan and his adviser, Nadia Heninger, 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.

    Past work has followed a similar approach: A 2021 paper 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. “I’m really happy someone did it,” said Thomas Espitau, a cryptography researcher at the company PQShield and an author of the 2021 version. His team’s work offered a “proof of concept,” he said; the new result shows that “you can do very fast lattice reduction in a sound way.”

    The new technique has already started to prove useful. Aurel Page, 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.

    LLL-style algorithms can also play a role in research related to lattice-based cryptography systems designed to remain secure even in a future with powerful quantum computers. They don’t 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 “basic building block,” said Wessel van Woerden, 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.


    Original story reprinted with permission from Quanta Magazine, an editorially independent publication of the Simons Foundation whose mission is to enhance public understanding of science by covering research developments and trends in mathematics and the physical and life sciences.

    Share. Facebook Twitter Pinterest LinkedIn WhatsApp Reddit Email
    Previous ArticleThe Best Sex Toys for Every Body
    Next Article DOJ’s Jonathan Kanter on the Google antitrust cases and fighting Big Tech’s monopoly power

    Related Posts

    ICE Has Spyware Now

    September 9, 2025

    US Congressman’s Brother Lands No-Bid Contract to Train DHS Snipers

    September 9, 2025

    No, Trump Can’t Legally Federalize US Elections

    September 6, 2025

    SSA Whistleblower’s Resignation Email Mysteriously Disappeared From Inboxes

    September 6, 2025

    Automated Sextortion Spyware Takes Webcam Pics of Victims Watching Porn

    September 5, 2025

    How to Stop Using Passwords and Start Using Passkeys

    September 5, 2025
    Our Picks

    You can now preorder the Apple Watch SE 3, Series 11, and Ultra 3

    September 9, 2025

    Psychological Tricks Can Get AI to Break the Rules

    September 9, 2025

    Apple is giving iPhone 14 and 15 users another free year of satellite features

    September 9, 2025

    Apple says the iPhone 17 comes with a massive security upgrade

    September 9, 2025
    • Facebook
    • Twitter
    • Pinterest
    • Instagram
    • YouTube
    • Vimeo
    Don't Miss
    News

    The iPhone 17 Pro’s orange is good — and well-timed

    By News RoomSeptember 9, 2025

    Apple just announced arguably its boldest Pro iPhone color ever: the new “cosmic orange” for…

    These Newly Discovered Cells Breathe in Two Ways

    September 9, 2025

    Apple’s newest health-tracking features are coming to older watches

    September 9, 2025

    The iPhone Air’s battery pack is slim, but not as slim as the iPhone Air

    September 9, 2025
    Facebook X (Twitter) Instagram Pinterest
    • Privacy Policy
    • Terms of use
    • Advertise
    • Contact
    © 2025 Technology Mag. All Rights Reserved.

    Type above and press Enter to search. Press Esc to cancel.