Spørgsmål og svar:Algoritme til at tjene som kryptografistandard for kvantecomputere

Matematikere arbejder ofte i uklarhed, og det er sandsynligvis, fordi få mennesker, bortset fra andre matematikere, der deler samme sub-speciale, forstår, hvad de laver. Selv når algoritmer har praktiske anvendelser, som at hjælpe chauffører med at se nærgående biler, som øjet ikke kan skelne, er det bilproducenten (eller dens softwareudvikler), der får æren.

Dette gælder især for kryptografer, de usungne helte, hvis algoritmer holder folks kommunikation og data sikre, når de bruger internettet – teknologi kendt som offentlig nøglekryptering.

Men nogle gange påvirker ren matematik den virkelige verden. Det skete denne sommer, da National Institute of Standards and Technologies valgte fire kryptografiske algoritmer til at fungere som standarder for offentlig nøglesikkerhed i den forestående æra af kvantecomputere, som vil gøre nuværende krypteringssystemer hurtigt forældede.

Tre af de fire valgte algoritmer hviler på arbejde ledet af et team af matematikere hos Brown:professorerne Jeffrey Hoffstein, Joseph Silverman og Jill Pipher (der også fungerer som Browns vicepræsident for forskning).

Historien om den NIST-godkendte Falcon-algoritme - og NTRU, det offentlige nøglekryptosystem, som Falcon er baseret på - begyndte i midten af ​​90'erne, da kvanteberegning stadig var i science fiction-området. På det tidspunkt var Hoffsteins mål at udvikle en algoritme til at forenkle og fremskynde den måde, konventionelle kryptografiske algoritmer fungerede på; i 1996 grundlagde han NTRU Cryptosystems Inc. sammen med Silverman og Pipher (som også er gift med Hoffstein) for at bringe det på markedet. Hoffstein sagde, at historien om NTRU er en "blodstødende saga", men virksomheden havde i sidste ende succes med at finde en passende køber i Qualcomm. Falcon, som Hoffstein co-designede med ni andre kryptografer, og to ud af de tre andre algoritmer NIST valgte, er bygget på den originale NTRU-ramme.

Fra før hans ph.d.-studium ved MIT gennem hver af de stillinger, han har haft ved Institute for Advanced Study, Cambridge University, University of Rochester og Brown, har Hoffstein været "en talfyr" gennem og igennem:"Det faldt mig aldrig ind for mig. ikke at være matematiker," sagde han. "Jeg lovede mig selv, at jeg ville fortsætte med at lave matematik, indtil det ikke længere var sjovt. Desværre er det stadig sjovt!"

I hælene på NIST's udvælgelse beskrev Hoffstein sin transformation fra talteoretiker til anvendt matematiker med en løsning på et forestående globalt problem af kritisk betydning.

Sp:Hvad er offentlig nøglekryptering?

Når du opretter forbindelse til Amazon for at foretage et køb, hvordan ved du så, at du virkelig er forbundet til Amazon, og ikke en falsk hjemmeside, der er konfigureret til at ligne Amazon? Så, når du sender dine kreditkortoplysninger, hvordan sender du dem så uden frygt for at blive opsnappet og stjålet? Det første spørgsmål løses ved, hvad der er kendt som en digital signatur; det andet løses ved offentlig nøglekryptering. Af NIST's standardiserede algoritmer er den ene til offentlig nøglekryptering, og de tre andre, inklusive Falcon, er til digitale signaturer.

Grunden til disse er problemer med ren matematik af en helt særlig type. De er svære at løse (tænk:tid indtil universet slutter), hvis du har én information, og de er nemme at løse (tager mikrosekunder), hvis du har en ekstra hemmelig information. Det vidunderlige er, at kun én af parterne, der kommunikerer – Amazon, i dette tilfælde – skal have den hemmelige information.

Sp:Hvad er den sikkerhedsudfordring, som kvantecomputere udgør?

Uden en tilstrækkelig stærk kvantecomputer er tiden til at løse krypteringsproblemet evigheder. Med en stærk kvantecomputer kommer tiden til at løse problemet ned til timer eller mindre. For at sige det mere alarmerende, hvis nogen havde besiddelse af en stærk kvantecomputer, ville hele internettets sikkerhed bryde fuldstændigt sammen. Og National Security Agency og store virksomheder satser på, at der inden for fem år er en god chance for, at der kan bygges en kvantecomputer, der er stærk nok til at bryde internettet.

Sp:Du kom med NTRU-løsningen i begyndelsen til midten af ​​90'erne, i god tid før nogen tænkte på kryptografibehovene for potentielle kvantecomputere. Hvad tænkte du på det tidspunkt?

Jeg fandt de tre hovedtilgange til offentlig nøglekryptografi meget klodsede og uæstetiske. Ligesom et eksempel går den mest kendte metode, RSA, ud på at tage tal, der er mange hundrede cifre lange, og derefter hæve dem til potenser, der er hundrede af cifre lange, dividere med endnu et tal, der er hundredvis af cifre, og endelig tager resten. Denne beregning er let gennemførlig på en computer, men ikke særlig praktisk, hvis du har en lille letvægtsprocessor, som en mobiltelefon fra 1996. RSA er også meget langsom – okay, millisekunder, men det tæller stadig som langsomt.

Vores drøm var at finde en metode til at lave offentlig nøglekryptering, der var størrelsesordener hurtigere end RSA og kunne køre på enheder med lav effekt. Og vi gjorde det! Folk, der implementerede det, var i stand til at køre det med hastigheder 200 til 300 gange hurtigere end RSA. Jeg gjorde det ikke alene – jeg tænkte besat over problemet i halvandet år, men det smeltede ikke sammen til en løsning, før jeg sluttede mig til Joe Silverman og Jill Pipher, mine Brown-kolleger og medstifterne af NTRU .

Sp:Hvad står NTRU for?

Vi sagde aldrig - folk antog bare, at vi mente noget teknisk og brugte deres fantasi! Men det står for "Number Theorists R Us." Dette irriterede Jill, da hun er en harmonisk analytiker, ikke en talteoretiker, men hun tilgav mig til sidst.

Spørgsmål:Du har beskrevet din start-up NTRU Cryptosystems som at have omkring fem "nær døden" oplevelser. Hvad var nogle af de udfordringer, du stod over for?

Portvagterne på området er for det meste kryptografer, der arbejder for virksomheder og i datalogiske afdelinger. Det er utroligt svært at få en ny algoritme til at blive taget seriøst, og det er især svært, hvis du ikke er i kryptografiklubben. I vores tilfælde ringede vi med alarmklokkerne af to årsager. Vi var for eksempel outsidere, og vi tilføjede ekstra struktur fra algebraisk talteori til gitter for at gøre tingene mere effektive.

Når du gør det, er der en alvorlig risiko for, at du ved et uheld har introduceret svagheder. Ja, det er vidunderligt at gøre noget mere effektivt. Men har du mistet et vigtigt stykke sikkerhed i processen? Det er fuldstændig forståeligt, at folk var dybt mistænksomme over for denne ekstra struktur, som introducerede evnen til at multiplicere såvel som at tilføje. Det tog 10 år med intens granskning, før folk begyndte at acceptere, at der ikke var tilføjet nogen svagheder.

Sp:Dette var ikke kun en akademisk øvelse. NTRU var en virksomhed, der skulle arbejde med investorer og potentielle kunder. Tidligt blev NTRU uretfærdigt under angreb i et papir skrevet af nogle kendte navne i kryptografi (som senere erkendte deres fejl). Hvordan overlevede NTRU det?

Det viste sig, at deres papir stort set blev ignoreret, men vores papir var tilstrækkelig interessant til, at alle dykkede ind i det. De forsøgte at angribe og ødelægge det, og det fik en enorm opmærksomhed. Hver eneste overflade, du kan forestille dig, var omgivet af væddere. Kryptografisamfundet var så modstandsdygtigt over for matematikere, der trængte ind på deres græstæppe. Hvis vi ikke havde været kendte matematikere fra Brown, ville vi ikke have overlevet kontroversen. I sidste ende hjalp den opmærksomhed os nok.

Spørgsmål:Var der nogen måder, hvorpå det at være matematiker – outsidere, denne verden – var en fordel?

Det, jeg er mest stolt af, er ikke nødvendigvis det faktum, at den særlige algoritme endte i de sidste fire af NIST-valgene, selvom hver eneste af de tre gitterbaserede algoritmer bruger vores ringstruktur (multiplikationsfunktionen). De bruger alle den matematik, som vi introducerede, fordi efter mere end 25 års undersøgelse, er der ikke dukket en eneste svaghed op på grund af tilføjelsen af ​​den struktur. Den matematik, som kom fra algebraisk talteori, var ikke en del af kryptografi før. Det er en del af det, jeg gør for mit andet liv, og jeg finder det særligt dejligt, at vi var i stand til at tage denne fuldstændig abstrakte teoretiske ting af tilsyneladende ingen nytte og finde en praktisk anvendelse. Som et resultat skal den nuværende generation af kryptografer alle kende algebraisk teori, hvilket er lidt sjovt.

Sp:Hvordan er det at være gift med en anden matematiker?

Det er den mest salige ting i universet at være gift med en, der forstår, hvordan det er at være matematiker. I matematik bruger du 99,9 % af tiden timer, uger, måneder og år på at tænke på noget, der ikke bliver til noget. Så mange gange tror du, at du har en fantastisk idé, og den går ingen vegne. Det er vidunderligt at være gift med en, der forstår den følelse, selvom vi ikke altid forstår detaljerne i, hvad den anden arbejder på.

Spørgsmål:Hun indser, når du er fortabt i tanker?

Ja, og det er hun sikkert også. + Udforsk yderligere

NIST annoncerer de første fire kvanteresistente kryptografiske algoritmer