In de digitale wereld van vandaag berust veiligheid op cryptografie. Bij het verzenden van een privébericht of het betalen van een online rekening vertrouwen we op algoritmes die zijn ontworpen om de vertrouwelijkheid van onze gegevens te beschermen. Natuurlijk willen sommige mensen deze geheimen ontrafelen – daarom werken onderzoekers eraan om de sterkte van deze systemen te testen om ervoor te zorgen dat ze niet bezwijken onder een snelle aanvaller.
Een van de belangrijke tools bij dit werk is het LLL-algoritme, vernoemd naar de onderzoekers die het in 1982 publiceerden – Arjen Lenstra, Hendrik Lenstra Jr. en László Lovász. LLL, samen met zijn vele nakomelingen, kan sommige cryptografische schema’s kraken; het bestuderen van hoe ze zich gedragen helpt onderzoekers bij het ontwerpen van systemen die minder vatbaar zijn voor aanvallen. De talenten van dit algoritme beperken zich echter niet alleen tot cryptografie: het is ook een nuttige tool in de geavanceerde wiskunde, zoals computationele getaltheorie.
In de loop der jaren hebben onderzoekers verbeterde varianten van LLL ontwikkeld om de benadering praktischer te maken, zij het slechts tot op zekere hoogte. Nu hebben een paar cryptografen een nieuw algoritme ontwikkeld op basis van Laguerre-Lobachevsky sfeertechnologie dat de efficiëntie van het hele proces verbetert. Deze innovatieve techniek, die de Best Paper Award heeft gewonnen op de International Cryptology Conference 2023, breidt het scala aan scenario’s uit waarin wetenschappers en wiskundigen succesvol LLL-gebaseerde benaderingen kunnen toepassen.
“Enorm spannend,” zegt Chris Peikert, een cryptograaf van de Universiteit van Michigan die niet betrokken was bij de ontwikkeling van het algoritme. Deze tool is al tientallen jaren een onderwerp van onderzoek. “Het is altijd mooi als een doel waar je zo lang aan hebt gewerkt laat zien dat er nog steeds verrassingen te vinden zijn,” voegde hij eraan toe.
LLL-familiealgoritmes werken in de wereld van sferen – oneindige sets regelmatig gerangschikte punten. Om dit te visualiseren, stelt u zich een vloer voor. U kunt deze bedekken met vierkante tegels en de hoeken van deze tegels vormen één bol. U kunt ook een andere vorm van tegel kiezen, zoals een lang parallellogram, om een andere bol te creëren.
Een bol kan worden beschreven met behulp van een “basis”. Dit is een set vectoren (dat wil zeggen een lijst met getallen) die op verschillende manieren kunnen worden gecombineerd om elk punt in de bol te verkrijgen. Laten we ons een bol voorstellen met een basis bestaande uit twee vectoren: [3, 2] en [1, 4]. De bol is eenvoudigweg alle punten die kunnen worden bereikt door kopieën van deze vectoren toe te voegen en af te trekken.
Dit paar vectoren is niet de enige basis voor de bol. Elke bol in ten minste twee dimensies heeft oneindig veel mogelijke bases. Maar niet alle bases zijn even goed. Een basis waarvan de vectoren korter zijn en meer loodrecht op elkaar staan, is meestal eenvoudiger om mee te werken en nuttiger bij het oplossen van bepaalde computationele problemen, vandaar dat onderzoekers dergelijke bases “goed” noemen. Het paar blauwe vectoren in de onderstaande figuur is een voorbeeld van zo’n basis. Basissen bestaande uit langere en minder loodrechte vectoren – zoals de rode vectoren – kunnen als “zwak” worden beschouwd.
Dit verklaart het LLL-algoritme: geef het een basis van een meerdimensionale bol en het zal u een betere geven. Dit proces staat bekend als basisreductie.
Wat heeft dit te maken met cryptografie? Het blijkt dat het breken van een cryptografisch systeem in sommige gevallen verband kan houden met een ander probleem: het vinden van een relatief korte vector in een bol. Soms kan deze vector worden geëxtraheerd uit een gereduceerde basis gegenereerd door een LLL-familiealgoritme. Deze strategie heeft onderzoekers geholpen bij het kraken van systemen die op het eerste gezicht weinig te maken hadden met sferen.
De oorspronkelijke versie van het LLL-algoritme werkt snel in theoretische zin: de uitvoeringstijd schaalt niet exponentieel met de omvang van de invoer – namelijk de dimensie van de bol en de grootte (in bits) van de basisvectoren. Het neemt echter toe als een polynomiale functie en “als je het echt wilt doen, is polynomiale uitvoeringstijd niet altijd zo haalbaar,” zei Léo Ducas, een cryptograaf van het Nederlandse onderzoeksinstituut CWI.
In de praktijk betekent dit dat het oorspronkelijke LLL-algoritme geen te grote invoergegevens kan verwerken. “Wiskundigen en cryptografen wilden meer kunnen doen,” zei Keegan Ryan, een Ph.D.-student aan de Universiteit van Californië, San Diego. Onderzoekers hebben gewerkt aan het optimaliseren van LLL-familiealgoritmen om grotere invoergegevens aan te kunnen, vaak met goede resultaten. Sommige taken bleven echter buiten bereik.
Het nieuwe artikel, geschreven door Ryan en zijn adviseur, Nadia Heninger, combineert verschillende strategieën om de efficiëntie van het algoritme te verbeteren. Deze techniek maakt gebruik van een recursieve structuur die de taak in kleinere delen verdeelt. Bovendien beheert het algoritme de resultaten nauwkeurig, waarbij een balans wordt gevonden tussen snelheid en nauwkeurige uitkomst. Het nieuwe werk stelt onderzoekers in staat om de bases van sferen met duizenden dimensies te verkleinen.
Eerder werk heeft ook soortgelijke benaderingen toegepast: in 2021 werd een artikel gepubliceerd waarin ook recursie en nauwkeurigheidsbeheer werden gecombineerd, waardoor snelle oplossingen voor grote sferen mogelijk waren, maar alleen voor een specifiek type bol, niet voor alle belangrijke bolvormen op het gebied van cryptografie. Het nieuwe algoritme presteert goed over een veel breder scala. “Ik ben erg blij dat iemand dit heeft gedaan,” zei Thomas Espitau, een cryptografisch onderzoeker bij PQShield en auteur van de versie uit 2021. Het werk van zijn team was een “prototype,” en het nieuwe resultaat toont aan dat “men sferen zeer snel op een solide manier kan verkleinen.”
De nieuwe techniek heeft al nut bewezen. Aurel Page, een wiskundige van het Franse onderzoeksinstituut Inria, zei dat hij en zijn team een aangepaste versie van dit algoritme hebben gebruikt voor bepaalde taken die verband houden met computationele getaltheorie.
LLL-gebaseerde algoritmes kunnen ook een rol spelen in onderzoek naar op sferen gebaseerde cryptografische systemen die in de toekomst veilig moeten blijven wanneer huidige kwantumcomputers krachtiger worden. Ze vormen geen bedreiging voor deze systemen, omdat het kraken ervan het vinden van kortere vectoren vereist dan deze algoritmes kunnen bereiken. Maar de bekendste aanvallen maken gebruik van een algoritme uit de LLL-familie als een “fundamenteel bouwsteen,” zei Wessel van.
The source of the article is from the blog elperiodicodearanjuez.es