Berømt kryptografialgoritme får en opgradering | Quanta Magasinet

I vores stadig mere digitale liv afhænger sikkerheden af ​​kryptografi. Send en privat besked eller betal en regning online, og du er afhængig af algoritmer designet til at holde dine data hemmelige. Naturligvis ønsker nogle mennesker at afsløre disse hemmeligheder - så forskere arbejder på at teste styrken af ​​disse systemer for at sikre, at de ikke smuldrer i hænderne på en klog angriber.

Et vigtigt værktøj i dette arbejde er LLL-algoritmen, opkaldt efter de forskere, der offentliggjort det i 1982 — Arjen Lenstra, Hendrik Lenstra Jr. og László Lovász. LLL, sammen med dets mange efterkommere, kan bryde kryptografiske skemaer i nogle tilfælde; at studere, hvordan de opfører sig, hjælper forskere med at designe systemer, der er mindre sårbare over for angreb. Og algoritmens talenter strækker sig ud over kryptografi: Det er også et nyttigt værktøj i avancerede matematiske arenaer såsom beregningsmæssig talteori.

Gennem årene har forskere finpudset varianter af LLL for at gøre tilgangen mere praktisk - men kun op til et punkt. Nu har et par kryptografer bygget en ny LLL-stil algoritme med et betydeligt løft i effektivitet. Den nye teknik, der vandt Pris for bedste papir ved International Kryptologi konference 2023, udvider rækken af ​​scenarier, hvor dataloger og matematikere kan bruge LLL-lignende tilgange.

"Det var virkelig spændende," sagde Chris Peikert, en kryptograf ved University of Michigan, som ikke var involveret i papiret. Værktøjet har været fokus for undersøgelsen i årtier, sagde han. "Det er altid rart, når et mål, der har været arbejdet på så længe ... viser, at der stadig er overraskelser at finde."

Algoritmer af LLL-typen fungerer i gitterverdenen: uendelige samlinger af punkter med regelmæssig afstand. Som en måde at visualisere dette på, forestil dig, at du fliser et gulv. Du kunne dække det med firkantede fliser, og hjørnerne af disse fliser ville udgøre et gitter. Alternativt kan du vælge en anden fliseform - for eksempel et langt parallelogram - for at skabe et andet gitter.

Et gitter kan beskrives ved at bruge dets "grundlag". Dette er et sæt vektorer (i det væsentlige lister over tal), som du kan kombinere på forskellige måder for at få hvert punkt i gitteret. Lad os forestille os et gitter med en basis bestående af to vektorer: [3, 2] og [1, 4]. Gitteret er bare alle de punkter, du kan nå ved at tilføje og trække kopier af disse vektorer fra.

Det par af vektorer er ikke gitterets eneste grundlag. Hvert gitter med mindst to dimensioner har uendeligt mange mulige baser. Men ikke alle baser er skabt lige. En basis, hvis vektorer er kortere og tættere på rette vinkler med hinanden, er normalt lettere at arbejde med og mere nyttig til at løse nogle beregningsmæssige problemer, så forskere kalder disse baser "gode". Et eksempel på dette er parret af blå vektorer i figuren nedenfor. Baser bestående af længere og mindre ortogonale vektorer - ligesom de røde vektorer - kan betragtes som "dårlige".

Dette er et job for LLL: Giv det (eller dets brødre) et grundlag af et multidimensionelt gitter, og det vil spytte et bedre ud. Denne proces er kendt som gitterbasisreduktion.

Hvad har det hele at gøre med kryptografi? Det viser sig, at opgaven med at bryde et kryptografisk system i nogle tilfælde kan omformes som et andet problem: at finde en relativt kort vektor i et gitter. Og nogle gange kan den vektor plukkes fra den reducerede basis genereret af en LLL-stil algoritme. Denne strategi har hjulpet forskere med at vælte systemer, der på overfladen ser ud til at have lidt at gøre med gitter.

I teoretisk forstand kører den originale LLL-algoritme hurtigt: Den tid, det tager at køre, skaleres ikke eksponentielt med størrelsen af ​​inputtet - det vil sige dimensionen af ​​gitteret og størrelsen (i bits) af tallene i basisvektorer. Men det øges som en polynomiel funktion, og "hvis du faktisk ønsker at gøre det, er polynomiel tid ikke altid så gennemførlig," sagde Léo Ducas, en kryptograf ved det nationale forskningsinstitut CWI i Holland.

I praksis betyder det, at den originale LLL-algoritme ikke kan håndtere input, der er for store. "Matematikere og kryptografer ønskede evnen til at gøre mere," sagde Keegan Ryan, en ph.d.-studerende ved University of California, San Diego. Forskere arbejdede på at optimere LLL-lignende algoritmer til at rumme større input, hvilket ofte opnåede god ydeevne. Alligevel har nogle opgaver været stædigt uden for rækkevidde.

Det nye papir, forfattet af Ryan og hans rådgiver, Nadia Heninger, kombinerer flere strategier for at forbedre effektiviteten af ​​sin LLL-stil algoritme. For det første bruger teknikken en rekursiv struktur, der deler opgaven ned i mindre bidder. For det andet styrer algoritmen omhyggeligt præcisionen af ​​de involverede tal, og finder en balance mellem hastighed og et korrekt resultat. Det nye arbejde gør det muligt for forskere at reducere baserne af gitter med tusindvis af dimensioner.

Tidligere arbejde har fulgt en lignende tilgang: A 2021 papir kombinerer også rekursion og præcisionsstyring for at gøre hurtigt arbejde med store gitter, men det fungerede kun for specifikke slags gitter, og ikke alle dem, der er vigtige i kryptografi. Den nye algoritme opfører sig godt på et meget bredere område. "Jeg er virkelig glad for, at nogen gjorde det," sagde Thomas Espitau, en kryptografiforsker hos virksomheden PQShield og en forfatter til 2021-versionen. Hans teams arbejde tilbød et "proof of concept," sagde han; det nye resultat viser, at "du kan lave meget hurtig gitterreduktion på en forsvarlig måde."

Den nye teknik er allerede begyndt at vise sig nyttig. Aurel Page, en matematiker ved det franske nationale forskningsinstitut Inria, sagde, at han og hans team har lavet en tilpasning af algoritmen til at arbejde på nogle beregningsmæssige talteoretiske opgaver.

LLL-stil algoritmer kan også spille en rolle i forskning relateret til gitterbaserede kryptografiske systemer designet til at forblive sikre selv i en fremtid med kraftige kvantecomputere. De udgør ikke en trussel mod sådanne systemer, da nedtagning af dem kræver at finde kortere vektorer, end disse algoritmer kan opnå. Men de bedste angreb, forskere kender til, bruger en LLL-stil algoritme som en "grundlæggende byggesten," sagde Wessel van Woerden, en kryptograf ved universitetet i Bordeaux. I praktiske eksperimenter for at studere disse angreb, kan den byggesten bremse alt. Ved at bruge det nye værktøj kan forskere muligvis udvide rækken af ​​eksperimenter, de kan køre på angrebsalgoritmerne, hvilket giver et klarere billede af, hvordan de klarer sig.

Quanta gennemfører en række undersøgelser for bedre at kunne betjene vores publikum. Tag vores datalogisk læserundersøgelse og du vil være med til at vinde gratis Quanta varer.