Berømt kryptografialgoritme får en oppgradering | Quanta Magazine

I våre stadig mer digitale liv er sikkerhet avhengig av kryptografi. Send en privat melding eller betal en regning på nettet, og du er avhengig av algoritmer designet for å holde dataene dine hemmelige. Naturligvis ønsker noen mennesker å avdekke disse hemmelighetene - så forskere jobber med å teste styrken til disse systemene for å sikre at de ikke smuldrer opp i hendene på en smart angriper.

Et viktig verktøy i dette arbeidet er LLL-algoritmen, oppkalt etter forskerne som publiserte den i 1982 — Arjen Lenstra, Hendrik Lenstra Jr. og László Lovász. LLL, sammen med sine mange etterkommere, kan bryte kryptografiske skjemaer i noen tilfeller; å studere hvordan de oppfører seg hjelper forskere med å designe systemer som er mindre sårbare for angrep. Og algoritmens talenter strekker seg utover kryptografi: Det er også et nyttig verktøy på avanserte matematiske arenaer som beregningstallteori.

Gjennom årene har forskere finpusset varianter av LLL for å gjøre tilnærmingen mer praktisk - men bare opp til et punkt. Nå har et par kryptografer bygget en ny LLL-stil algoritme med et betydelig løft i effektivitet. Den nye teknikken, som vant Pris for beste papir på Internasjonal kryptologikonferanse 2023, utvider utvalget av scenarier der informatikere og matematikere kan bruke LLL-lignende tilnærminger.

"Det var veldig spennende," sa Chris Peikert, en kryptograf ved University of Michigan som ikke var involvert i avisen. Verktøyet har vært fokus for studier i flere tiår, sa han. "Det er alltid hyggelig når et mål som har vært jobbet med så lenge ... viser at det fortsatt er overraskelser å finne."

Algoritmer av LLL-typen opererer i gitterverdenen: uendelige samlinger av punkter med jevne mellomrom. Som en måte å visualisere dette på, se for deg at du fliser et gulv. Du kan dekke den med firkantede fliser, og hjørnene på disse flisene vil utgjøre ett gitter. Alternativt kan du velge en annen flisform - for eksempel et langt parallellogram - for å lage et annet gitter.

Et gitter kan beskrives ved å bruke dets "grunnlag". Dette er et sett med vektorer (i hovedsak lister med tall) som du kan kombinere på forskjellige måter for å få hvert punkt i gitteret. La oss forestille oss et gitter med en basis som består av to vektorer: [3, 2] og [1, 4]. Gitteret er bare alle punktene du kan nå ved å legge til og trekke fra kopier av disse vektorene.

Det vektorparet er ikke gitterets eneste grunnlag. Hvert gitter med minst to dimensjoner har uendelig mange mulige baser. Men ikke alle baser er skapt like. Et grunnlag hvis vektorer er kortere og nærmere rette vinkler med hverandre, er vanligvis lettere å jobbe med og mer nyttig for å løse noen beregningsproblemer, så forskere kaller disse basene "gode". Et eksempel på dette er paret med blå vektorer i figuren nedenfor. Baser som består av lengre og mindre ortogonale vektorer - som de røde vektorene - kan betraktes som "dårlige".

Dette er en jobb for LLL: Gi den (eller dens brødre) et grunnlag av et flerdimensjonalt gitter, og det vil spytte ut et bedre. Denne prosessen er kjent som gitterbasisreduksjon.

Hva har alt dette med kryptografi å gjøre? Det viser seg at oppgaven med å bryte et kryptografisk system i noen tilfeller kan omformes som et annet problem: å finne en relativt kort vektor i et gitter. Og noen ganger kan den vektoren plukkes fra den reduserte basisen generert av en LLL-stil algoritme. Denne strategien har hjulpet forskere med å velte systemer som på overflaten ser ut til å ha lite med gitter å gjøre.

I teoretisk forstand kjører den opprinnelige LLL-algoritmen raskt: Tiden det tar å kjøre skaleres ikke eksponentielt med størrelsen på inngangen - det vil si dimensjonen til gitteret og størrelsen (i biter) av tallene i basisvektorer. Men det øker som en polynomfunksjon, og "hvis du faktisk vil gjøre det, er polynomtid ikke alltid så gjennomførbart," sa Léo Ducas, en kryptograf ved det nasjonale forskningsinstituttet CWI i Nederland.

I praksis betyr dette at den originale LLL-algoritmen ikke kan håndtere innganger som er for store. "Matematikere og kryptografer ønsket muligheten til å gjøre mer," sa Keegan Ryan, en doktorgradsstudent ved University of California, San Diego. Forskere jobbet for å optimalisere LLL-stil algoritmer for å imøtekomme større innganger, ofte oppnå god ytelse. Likevel har noen oppgaver holdt seg hardnakket utenfor rekkevidde.

Det nye papiret, skrevet av Ryan og hans rådgiver, Nadia Heninger, kombinerer flere strategier for å forbedre effektiviteten til sin LLL-stil algoritme. For det første bruker teknikken en rekursiv struktur som bryter oppgaven ned i mindre biter. For en annen styrer algoritmen nøyaktig presisjonen til tallene som er involvert, og finner en balanse mellom hastighet og et riktig resultat. Det nye arbeidet gjør det mulig for forskere å redusere basene til gitter med tusenvis av dimensjoner.

Tidligere arbeid har fulgt en lignende tilnærming: A 2021 papir kombinerer også rekursjon og presisjonsstyring for å gjøre raskt arbeid med store gitter, men det fungerte bare for spesifikke typer gitter, og ikke alle de som er viktige i kryptografi. Den nye algoritmen oppfører seg bra på et mye bredere område. "Jeg er veldig glad for at noen gjorde det," sa Thomas Espitau, en kryptografiforsker ved selskapet PQShield og en forfatter av 2021-versjonen. Hans teams arbeid tilbød et "proof of concept," sa han; det nye resultatet viser at "du kan gjøre veldig rask gitterreduksjon på en god måte."

Den nye teknikken har allerede begynt å vise seg nyttig. Aurel Page, en matematiker ved det franske nasjonale forskningsinstituttet Inria, sa at han og teamet hans har tilpasset algoritmen for å jobbe med noen beregningsmessige tallteorioppgaver.

Algoritmer i LLL-stil kan også spille en rolle i forskning relatert til gitterbaserte kryptografisystemer designet for å forbli sikker selv i en fremtid med kraftige kvantedatamaskiner. De utgjør ingen trussel mot slike systemer, siden å fjerne dem krever å finne kortere vektorer enn disse algoritmene kan oppnå. Men de beste angrepsforskerne vet om bruker en LLL-stil algoritme som en "grunnleggende byggestein," sa Wessel van Woerden, en kryptograf ved universitetet i Bordeaux. I praktiske eksperimenter for å studere disse angrepene, kan den byggesteinen bremse alt. Ved å bruke det nye verktøyet kan forskere kanskje utvide spekteret av eksperimenter de kan kjøre på angrepsalgoritmene, og gi et klarere bilde av hvordan de presterer.

Quanta gjennomfører en serie undersøkelser for å tjene publikum bedre. Ta vår informatikk leserundersøkelse og du vil bli registrert for å vinne gratis Quanta handelsvarer.