Algoritme for å tjene som kryptografistandard for kvanteberegningstiden

Matematikere sliter ofte i uklarhet, og det er sannsynligvis fordi få mennesker, bortsett fra andre matematikere som deler samme sub-spesialitet, forstår hva de gjør. Selv når algoritmer har praktiske applikasjoner, som å hjelpe sjåfører med å se nærmer seg biler som øyet ikke kan skjelne, er det bilprodusenten (eller dens programvareutvikler) som får æren.

Dette gjelder spesielt kryptografer, de ukjente heltene hvis algoritmer holder folks kommunikasjon og data sikker når de bruker internett – teknologi kjent som offentlig nøkkelkryptering.

Men noen ganger påvirker ren matematikk den virkelige verden. Det skjedde i sommer da National Institute of Standards and Technologies valgte ut fire kryptografiske algoritmer å tjene som standarder for offentlig nøkkelsikkerhet i den forestående epoken med kvantedatamaskiner, noe som vil gjøre dagens krypteringssystemer raskt foreldet.

Tre av de fire valgte algoritmene hviler på arbeid ledet av et team av matematikere ved Brown: professorene Jeffrey Hoffstein, Joseph Silverman og Jill Pipher (som også fungerer som Browns visepresident for forskning).

Historien om NIST-godkjent Falcon algoritme– og NTRU, det offentlige nøkkelkryptosystemet som Falcon er basert på – begynte på midten av 90-tallet, da kvanteberegning var fortsatt i science fiction-riket. På den tiden var Hoffsteins mål å utvikle en algoritme for å forenkle og fremskynde måten konvensjonelle kryptografiske algoritmer fungerte på; i 1996 grunnla han NTRU Cryptosystems Inc. sammen med Silverman og Pipher (som også er gift med Hoffstein) for å ta det ut på markedet. Hoffstein sa at historien til NTRU er en “blodsvulstende saga”, men selskapet var til slutt vellykket, og fant en passende kjøper i Qualcomm. Falcon, som Hoffstein co-designet med ni andre kryptografer, og to av de tre andre algoritmene NIST valgte, er bygget på det originale NTRU-rammeverket.

Fra før doktorgradsstudiet ved MIT gjennom hver av stillingene han har hatt ved Institute for Advanced Study, Cambridge University, University of Rochester og Brown, har Hoffstein vært «en tallfyr» gjennom og gjennom: «Det falt meg aldri inn. ikke å være matematiker,” sa han. “Jeg lovet meg selv at jeg skulle fortsette å gjøre matte til det ikke lenger var gøy. Dessverre er det fortsatt gøy!”

I hælene på NISTs utvalg beskrev Hoffstein sin transformasjon fra en tallteoretiker til en anvendt matematiker med en løsning på et forestående globalt problem av kritisk betydning.

Spørsmål: Hva er offentlig nøkkelkryptering?

Når du kobler til Amazon for å foreta et kjøp, hvordan vet du at du virkelig er koblet til Amazon, og ikke et falskt nettsted satt opp til å se akkurat ut som Amazon? Så, når du sender kredittkortinformasjonen din, hvordan sender du den uten frykt for at den blir avlyttet og stjålet? Det første spørsmålet løses av det som kalles en digital signatur; den andre løses med offentlig nøkkelkryptering. Av NISTs standardiserte algoritmer er en for offentlig nøkkelkryptering, og de tre andre, inkludert Falcon, er for digitale signaturer.

Til grunn for disse ligger problemer med ren matematikk av en helt spesiell type. De er vanskelige å løse (tenk: tid til universet tar slutt) hvis du har én informasjon og de er enkle å løse (tar mikrosekunder) hvis du har en ekstra hemmelig informasjon. Det fantastiske er at bare én av partene som kommuniserer – Amazon, i dette tilfellet – trenger å ha den hemmelige informasjonen.

Spørsmål: Hva er sikkerhetsutfordringen som kvantedatamaskiner utgjør?

Uten en tilstrekkelig sterk kvantedatamaskin er tiden for å løse krypteringsproblemet evigheter. Med en sterk kvantedatamaskin kommer tiden til å løse problemet ned til timer eller mindre. For å si det mer alarmerende, hvis noen hadde en sterk kvantedatamaskin, ville hele sikkerheten til internett brytes fullstendig sammen. Og National Security Agency og store selskaper satser på at det innen fem år er en god sjanse for at det kan bygges en kvantedatamaskin som er sterk nok til å bryte internett.

Spørsmål: Du kom opp med NTRU-løsningen tidlig til midten av 90-tallet, i god tid før noen tenkte på kryptografibehovene til potensielle kvantedatamaskiner. Hva tenkte du på den tiden?

Jeg syntes de tre hovedtilnærmingene til offentlig nøkkelkryptering var veldig klønete og uestetiske. Akkurat som ett eksempel, går den mest kjente metoden, RSA, ut på å ta tall som er mange hundre siffer lange, for så å heve dem til potenser som er hundrevis av siffer lange, dividere med enda et tall som er hundrevis av siffer, og tar til slutt resten. Denne beregningen er lett gjennomførbar på en datamaskin, men ikke veldig praktisk hvis du har en liten, lett prosessor, som en mobiltelefon fra 1996. RSA er også veldig treg – ok, millisekunder, men det teller fortsatt som tregt.

Drømmen vår var å finne en metode for å utføre offentlig nøkkelkryptering som var størrelsesordener raskere enn RSA og kunne kjøre på enheter med lav effekt. Og vi klarte det! Folk som implementerte den var i stand til å kjøre den med hastigheter 200 til 300 ganger raskere enn RSA. Jeg gjorde ikke dette alene – jeg tenkte obsessivt på problemet i halvannet år, men det gikk ikke sammen til en løsning før jeg ble sammen med Joe Silverman og Jill Pipher, mine Brown-kolleger og medgründerne av NTRU .

Spørsmål: Hva står NTRU for?

Vi sa aldri – folk bare antok at vi mente noe teknisk og brukte fantasien deres! Men det står for “Number Theorists R Us.” Dette irriterte Jill ettersom hun er en harmonisk analytiker, ikke en tallteoretiker, men hun tilga meg til slutt.

Spørsmål: Du har beskrevet oppstarten din NTRU Cryptosystems som å ha omtrent fem “nesten døden”-opplevelser. Hva var noen av utfordringene du møtte?

Portvaktene i feltet er stort sett kryptografer som jobber for bedrifter og i informatikkavdelinger. Det er utrolig vanskelig å få noen ny algoritme til å bli tatt på alvor, og det er spesielt vanskelig hvis du ikke er i kryptografiklubben. I vårt tilfelle ringte vi alarmklokker av to grunner. Vi var outsidere, for en, og vi la til ekstra struktur fra algebraisk tallteori til gitter for å gjøre ting mer effektivt.

Når du gjør det, er det en alvorlig risiko for at du ved et uhell har introdusert svakheter. Ja, det er fantastisk å gjøre noe mer effektivt. Men har du mistet en viktig del av sikkerheten i prosessen? Det er helt forståelig at folk var dypt mistenksomme overfor denne ekstra strukturen, som introduserte muligheten til å multiplisere så vel som å legge til. Det tok 10 år med intens gransking før folk begynte å akseptere at ingen svakheter var lagt til.

Spørsmål: Dette var ikke bare en akademisk øvelse. NTRU var et selskap som måtte jobbe med investorer og potensielle kunder. Tidlig ble NTRU urettmessig angrepet i en artikkel skrevet av noen kjente navn innen kryptografi (som senere erkjente feilen deres). Hvordan overlevde NTRU det?

Det viste seg at papiret deres stort sett ble ignorert, men papiret vårt var interessant nok til at alle gikk inn i det. De prøvde å angripe og ødelegge den, og den fikk enorm oppmerksomhet. Hver eneste overflate du kan forestille deg var preget av ramser. Kryptografisamfunnet var så motstandsdyktig mot matematikere som trengte inn på gressbanen deres. Hvis vi ikke hadde vært kjente matematikere fra Brown, ville vi ikke ha overlevd kontroversen. Til slutt hjalp nok den oppmerksomheten oss.

Spørsmål: Var det noen måter det var en fordel å være matematikere – utenforstående, denne verden på?

Det jeg er stoltest av er ikke nødvendigvis det faktum at den bestemte algoritmen havnet i de fire siste av NIST-valgene, selv om hver eneste av de tre gitterbaserte algoritmene bruker vår ringstruktur (multiplikasjonsfunksjonen). De bruker alle matematikken vi introduserte fordi etter mer enn 25 år med gransking, har ikke en eneste svakhet dukket opp på grunn av å legge til den strukturen. Den matematikken, som kom fra algebraisk tallteori, var ikke en del av kryptografi før. Det er en del av det jeg gjør for mitt andre liv, og jeg synes det er spesielt hyggelig at vi var i stand til å ta denne fullstendig abstrakte teoretiske tingen som tilsynelatende ikke har noen som helst nytte og finne en praktisk anvendelse. Som et resultat må den nåværende generasjonen av kryptografer alle kunne algebraisk teori, noe som er litt morsomt.

Spørsmål: Hvordan er det å være gift med en annen matematiker?

Det er den mest salige tingen i universet å være gift med noen som forstår hvordan det er å være matematiker. I matematikk bruker du 99,9 % av tiden timer, uker, måneder og år på å tenke på noe som ikke blir til noe. Så mange ganger tror du at du har en fantastisk idé, og den går ingen vei. Det er fantastisk å være gift med noen som forstår den følelsen, selv om vi ikke alltid forstår detaljene i det den andre jobber med.

Q: Hun innser når du er fortapt i tankene?

Ja, og det er hun sikkert også.

---

---