In onze steeds digitalere levens is veiligheid afhankelijk van cryptografie. Stuur een privébericht of betaal online een rekening, en u vertrouwt op algoritmen die zijn ontworpen om uw gegevens geheim te houden. Natuurlijk willen sommige mensen deze geheimen blootleggen. Daarom testen onderzoekers de kracht van deze systemen om er zeker van te zijn dat ze niet instorten door een slimme aanvaller.

Een belangrijk hulpmiddel in dit werk is het LLL-algoritme, genoemd naar de onderzoekers die publiceerde het in 1982 - Arjen Lenstra, Hendrik Lenstra Jr. en László Lovász. LLL kan, samen met zijn vele nakomelingen, in sommige gevallen cryptografische schema's doorbreken; Door te bestuderen hoe ze zich gedragen, kunnen onderzoekers systemen ontwerpen die minder kwetsbaar zijn voor aanvallen. En de talenten van het algoritme reiken verder dan cryptografie: het is ook een nuttig hulpmiddel in geavanceerde wiskundige arena's zoals computationele getaltheorie.

In de loop der jaren hebben onderzoekers varianten van LLL aangescherpt om de aanpak praktischer te maken – maar slechts tot op zekere hoogte. Nu hebben een paar cryptografen een nieuw algoritme in LLL-stijl gebouwd met een aanzienlijke efficiëntieverbetering. De nieuwe techniek, die de Prijs voor beste papier de Internationale cryptologieconferentie 2023, vergroot het scala aan scenario's waarin computerwetenschappers en wiskundigen op een praktische manier LLL-achtige benaderingen kunnen gebruiken.

“Het was echt spannend”, zei hij Chris Peikert, een cryptograaf aan de Universiteit van Michigan die niet bij het artikel betrokken was. De tool is al tientallen jaren het onderwerp van onderzoek, zei hij. “Het is altijd leuk als een doelwit waar zo lang aan gewerkt is... laat zien dat er nog steeds verrassingen te ontdekken zijn.”

LLL-type algoritmen zijn actief in de wereld van roosters: oneindige verzamelingen van op regelmatige afstanden geplaatste punten. Om dit te visualiseren kunt u zich voorstellen dat u een vloer aan het betegelen bent. Je zou het kunnen bedekken met vierkante tegels, en de hoeken van die tegels zouden één rooster vormen. Als alternatief kunt u een andere tegelvorm kiezen, bijvoorbeeld een lang parallellogram, om een ​​ander rooster te creëren.

Een rooster kan worden beschreven met behulp van zijn ‘basis’. Dit is een reeks vectoren (in wezen lijsten met getallen) die u op verschillende manieren kunt combineren om elk punt in het rooster te krijgen. Laten we ons een rooster voorstellen met een basis bestaande uit twee vectoren: [3, 2] en [1, 4]. Het rooster bestaat uit alle punten die u kunt bereiken door kopieën van die vectoren op te tellen en af ​​te trekken.

Dat paar vectoren is niet de enige basis van het rooster. Elk rooster met minstens twee dimensies heeft oneindig veel mogelijke bases. Maar niet alle bases zijn gelijk gemaakt. Een basis waarvan de vectoren korter zijn en dichter bij elkaar staan, is meestal gemakkelijker om mee te werken en nuttiger voor het oplossen van bepaalde rekenproblemen, dus noemen onderzoekers die bases ‘goed’. Een voorbeeld hiervan is het paar blauwe vectoren in de onderstaande figuur. Basen die uit langere en minder orthogonale vectoren bestaan ​​– zoals de rode vectoren – kunnen als ‘slecht’ worden beschouwd.

Dit is een taak voor LLL: geef het (of zijn broeders) een basis van een multidimensionaal rooster, en het zal een beter rooster uitspugen. Dit proces staat bekend als roosterbasisreductie.

Wat heeft dit allemaal met cryptografie te maken? Het blijkt dat de taak van het kraken van een cryptografisch systeem in sommige gevallen kan worden omgevormd tot een ander probleem: het vinden van een relatief korte vector in een rooster. En soms kan die vector worden geplukt uit de gereduceerde basis die wordt gegenereerd door een algoritme in LLL-stijl. Deze strategie heeft onderzoekers geholpen systemen omver te werpen die op het eerste gezicht weinig met roosters te maken lijken te hebben.

In theoretische zin werkt het oorspronkelijke LLL-algoritme snel: de tijd die nodig is om te worden uitgevoerd, schaalt niet exponentieel met de grootte van de invoer - dat wil zeggen de dimensie van het rooster en de grootte (in bits) van de getallen in de invoer. basisvectoren. Maar het neemt wel toe als een polynomiale functie, en “als je het echt wilt, is polynomiale tijd niet altijd zo haalbaar”, zei Leo Ducas, een cryptograaf bij het nationale onderzoeksinstituut CWI in Nederland.

In de praktijk betekent dit dat het oorspronkelijke LLL-algoritme niet overweg kan met te grote invoer. “Wiskundigen en cryptografen wilden meer kunnen doen”, zegt hij Keegan Ryan, een doctoraatsstudent aan de Universiteit van Californië, San Diego. Onderzoekers hebben gewerkt aan het optimaliseren van algoritmen in LLL-stijl om grotere invoer mogelijk te maken, waarbij vaak goede prestaties werden behaald. Toch zijn sommige taken hardnekkig buiten bereik gebleven.

Het nieuwe artikel, geschreven door Ryan en zijn adviseur, Nadia Henginger, combineert meerdere strategieën om de efficiëntie van zijn LLL-stijl algoritme te verbeteren. Om te beginnen maakt de techniek gebruik van een recursieve structuur die de taak in kleinere stukken opsplitst. Aan de andere kant beheert het algoritme zorgvuldig de nauwkeurigheid van de betrokken getallen, waarbij een balans wordt gevonden tussen snelheid en een correct resultaat. Het nieuwe werk maakt het voor onderzoekers haalbaar om de basis van roosters met duizenden dimensies te verkleinen.

Eerder werk heeft een soortgelijke aanpak gevolgd: A 2021 papier combineert ook recursie- en precisiebeheer om snel werk te maken van grote roosters, maar het werkte alleen voor specifieke soorten roosters, en niet voor alle roosters die belangrijk zijn in de cryptografie. Het nieuwe algoritme gedraagt ​​zich goed op een veel breder bereik. ‘Ik ben heel blij dat iemand het heeft gedaan’, zei hij Thomas Espitau, een cryptografieonderzoeker bij het bedrijf PQShield en auteur van de 2021-versie. Het werk van zijn team bood een ‘proof of concept’, zei hij; het nieuwe resultaat laat zien dat "je op een goede manier een zeer snelle roosterreductie kunt uitvoeren."

De nieuwe techniek begint al nuttig te blijken. Aurel Pagina, een wiskundige bij het Franse nationale onderzoeksinstituut Inria, zei dat hij en zijn team een ​​aanpassing van het algoritme hebben toegepast om te werken aan enkele computationele getaltheorietaken.

Algoritmen in LLL-stijl kunnen ook een rol spelen in onderzoek met betrekking tot op roosters gebaseerde cryptografiesystemen die daarvoor zijn ontworpen blijf veilig zelfs in een toekomst met krachtige kwantumcomputers. Ze vormen geen bedreiging voor dergelijke systemen, omdat het uitschakelen ervan kortere vectoren vereist dan deze algoritmen kunnen bereiken. Maar de beste aanvallen die onderzoekers kennen, gebruiken een algoritme in LLL-stijl als een ‘basisbouwsteen’ Wessel van Woerden, een cryptograaf aan de Universiteit van Bordeaux. In praktische experimenten om deze aanvallen te bestuderen, kan die bouwsteen alles vertragen. Met behulp van de nieuwe tool kunnen onderzoekers mogelijk het bereik van experimenten die ze kunnen uitvoeren met de aanvalsalgoritmen uitbreiden, waardoor een duidelijker beeld ontstaat van hoe ze presteren.

Quanta voert een reeks onderzoeken uit om ons publiek beter van dienst te zijn. Neem onze lezersenquête informatica en je doet mee om gratis te winnen Quanta handelswaar.