Dit is de taak voor LLL: geef hem (of zijn broers) de basis van een multidimensionaal rooster, en hij zal een beter rooster uitspugen. Dit proces staat bekend als roosterbasisreductie.
Wat heeft dit allemaal met cryptografie te maken? Het blijkt dat de taak om een cryptografisch systeem te kraken in sommige gevallen kan uitmonden in een ander probleem: het vinden van een relatief korte vector in het rooster. En soms kan die vector worden geëxtraheerd uit een gereduceerde basis die wordt gegenereerd door een algoritme in LLL-stijl. Deze strategie heeft onderzoekers geholpen systemen neer te halen die op het eerste gezicht weinig met roosters te maken lijken te hebben.
In theorie 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 basisvectoren. Maar het schaalt op als een polynomiale functie, en “als je het echt wilt, is polynomiale tijd niet altijd even haalbaar”, zegt Léo 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 Keegan Ryan, een doctoraalstudent 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. Sommige taken bleven echter koppig ongrijpbaar.
Het nieuwe artikel, geschreven door Ryan en zijn adviseur, Nadia Heninger, combineert meerdere strategieën om de efficiëntie van hun LLL-stijl algoritme te verbeteren. Ten eerste 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 correct resultaat. Het nieuwe werk stelt onderzoekers in staat roosterbasissen met duizenden dimensies te verkleinen.
Eerder werk volgde een vergelijkbare aanpak: het artikel uit 2021 combineert ook recursie en precisiesturing om een snelle werking van grote roosters mogelijk te maken, maar het werkte alleen voor bepaalde soorten roosters, die niet allemaal belangrijk zijn in de cryptografie. Het nieuwe algoritme presteert goed in een veel breder bereik. “Ik ben heel blij dat iemand het heeft gedaan”, zegt Thomas Espitau, cryptografieonderzoeker bij PQShield en auteur van de versie van 2021. Het werk van zijn team bood een “proof of concept”, zei hij; het nieuwe resultaat laat zien dat “je op een gezonde manier een zeer snelle roosterreductie kunt doen.”
De nieuwe techniek begint al nuttig te blijken. Aurel Page, een wiskundige bij het Franse nationale onderzoeksinstituut Inria, zei dat hij en zijn team het algoritme hebben aangepast om aan een aantal computationele getaltheorie-taken te werken.
Algoritmen in LLL-stijl kunnen ook een rol spelen in onderzoek met betrekking tot op roosters gebaseerde cryptografische systemen die zijn ontworpen om zelfs in een toekomst met krachtige kwantumcomputers veilig te blijven. Ze vormen geen bedreiging voor dergelijke systemen, omdat het verwijderen ervan kortere vectoren vereist dan deze algoritmen kunnen bereiken. Maar de beste aanvalsonderzoekers weten een algoritme in LLL-stijl te gebruiken als ‘basisbouwsteen’, zegt 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 aanvalsalgoritmen uitbreiden, waardoor een duidelijker beeld ontstaat van hoe ze presteren.
Origineel verhaal herdrukt met toestemming van Quanta-tijdschrift, redactioneel onafhankelijke uitgave Stichting Simmons wiens missie het is om het publieke begrip van wetenschap te verbeteren door onderzoeksontwikkelingen en trends in de wiskunde en de natuur- en levenswetenschappen te behandelen.