Introduksjon
I 1994, informatikeren Peter Shor oppdaget at hvis kvantedatamaskiner noen gang ble oppfunnet, ville de desimere mye av infrastrukturen som ble brukt for å beskytte informasjon som deles på nettet. Den skremmende muligheten har fått forskere til å kjempe for å produsere nye "post-kvante" krypteringssystemer, for å redde så mye informasjon de kunne fra å falle i hendene på kvantehackere.
Tidligere i år, National Institute of Standards and Technology avslørt fire finalister i sin søken etter en post-kvantekryptografistandard. Tre av dem bruker "gitterkryptografi" - et opplegg inspirert av gitter, vanlige arrangementer av prikker i rommet.
Gitterkryptografi og andre post-kvantemuligheter skiller seg fra gjeldende standarder på avgjørende måter. Men de er alle avhengige av matematisk asymmetri. Sikkerheten til mange nåværende kryptografisystemer er basert på multiplikasjon og faktorisering: Enhver datamaskin kan raskt multiplisere to tall, men det kan ta århundrer å faktorisere et kryptografisk stort tall inn i hovedbestanddelene. Den asymmetrien gjør hemmeligheter enkle å kode, men vanskelige å dekode.
Det Shor avslørte i sin algoritme fra 1994 var at et innfall med factoring gjør det sårbart for angrep fra kvantedatamaskiner. "Det er en veldig spesifikk, spesiell ting som kvantedatamaskinen kan gjøre," sa Katherine Stange, en matematiker ved University of Colorado, Boulder. Så etter Shor hadde kryptografer en ny jobb: Finn et nytt sett med matematiske operasjoner som er enkle å gjøre, men nesten umulige å angre.
Gitterkryptografi er et av de mest vellykkede forsøkene så langt. Opprinnelig utviklet på 1990-tallet, er den avhengig av vanskeligheten med å omvendt konstruere poengsum.
Her er en måte å beskrive gitterkryptografi på: Tenk deg at vennen din har et gitter, som bare er en haug med punkter i et vanlig, repeterende mønster over hele planet. Vennen din vil at du skal nevne 10 av disse punktene. Men han er vanskelig, og han vil ikke tegne hele gitteret. I stedet lister han opp bare to punkter - det første med en x-verdi på 101 og en y-verdi på 19, den andre med koordinater [235, 44].
Heldigvis er det lett å finne nye punkter på et gitter, for når du legger til og trekker fra to punkter på et gitter, får du et tredje poeng i samme gitter. Så alt du trenger å gjøre er å legge sammen poengene din venn ga deg, eller multiplisere dem med heltall og deretter legge dem sammen, eller en kombinasjon av de to. Gjør dette på åtte forskjellige måter, og du vil kunne svare på spørsmålet til vennen din.
Men vennen din er fortsatt ikke fornøyd. Han gir deg de samme to startpunktene, og spør deg deretter om punktet [2, 1] er på samme gitter. For å svare riktig på dette spørsmålet, må du finne kombinasjonen av [101, 19] og [235, 44] som gir [2, 1]. Dette problemet er mye vanskeligere enn det første, og du vil sannsynligvis ende opp med å bare gjette og sjekke for å få svaret.* Den asymmetrien er det som ligger til grunn for gitterkryptografi.
Hvis du faktisk vil bruke gitterkryptografi for å dele informasjon, gjør du følgende. Tenk deg at en venn (en bedre en!) ønsker å sende deg en sikker melding. Du starter med et kvadratisk rutenett av tall. Si at den har to rader og to kolonner, og ser slik ut:
Nå kommer du opp med en privat "nøkkel" som bare du kjenner. I dette eksemplet, la oss si at din private nøkkel bare er to hemmelige tall: 3 og −2. Du multipliserer tallene i den første kolonnen med 3, og tallene i den andre kolonnen med −2. Legg sammen resultatene i hver rad for å få en tredje kolonne med to oppføringer.
Fest den nye kolonnen på enden av rutenettet. Dette nye tre-kolonne rutenettet er din offentlige nøkkel. Del det fritt!
(Et scenario i den virkelige verden vil være litt mer komplisert. For å hindre hackere i å dekode den private nøkkelen din, må du legge til litt tilfeldig støy i den siste kolonnen. Men her skal vi ignorere det trinnet for enkelhets skyld. )
Nå vil vennen din bruke den offentlige nøkkelen til å sende deg en melding. Hun tenker på to egne hemmelige tall: 2 og 0. Hun multipliserer tallene i den første raden med 2, og de i den andre raden med 0. Hun legger så sammen resultatene i hver kolonne for å få en tredje rad.
Hun fester nå den nye raden til bunnen av rutenettet og sender den tilbake til deg. (Igjen, i et ekte system, må hun legge til litt støy til raden hennes.)
Nå skal du lese meldingen. For å gjøre dette, sjekker du om vennens siste rad er riktig. Bruk din egen private nøkkel på de to første oppføringene i raden hennes. Resultatet skal samsvare med den siste oppføringen.
Vennen din kan også velge å sende deg en rad med feil nummer i siste kolonne. Hun vet at dette tallet ikke stemmer overens med dine beregninger.
Hvis vennen din sender en rad der det siste tallet er riktig, tolker du dette som en 0. Hvis hun sender en rad der tallet er feil, tolker du det som en 1. Raden koder derfor en enkelt bit: enten 0 eller 1.
Merk at en ekstern angriper ikke vil ha tilgang til verken din private nøkkel eller vennens. Uten disse vil angriperen ikke ha noen anelse om det endelige tallet er riktig eller ikke.
I praksis vil du gjerne sende meldinger som er lengre enn én bit lange. Så folk som ønsker å motta, for eksempel, en 100-biters melding vil generere 100 nye kolonner i stedet for bare én. Deretter vil avsenderen av meldingen opprette en enkelt ny rad, og endre de siste 100 oppføringene for å kode enten en 0 eller en 1 for hver oppføring.
Hvis gitterkryptografi faktisk implementeres, vil den ha utallige nyanser som ikke dekkes i dette scenariet. For eksempel, hvis du vil at meldingen skal være virkelig trygg fra nysgjerrige øyne, må matrisen ha et utenkelig antall oppføringer, noe som gjør det hele så uhåndterlig at det ikke er verdt å bruke. For å komme rundt dette bruker forskerne matriser med nyttige symmetrier som kan kutte ned på antall parametere. Utover det er det en hel rekke justeringer som kan brukes på selve problemet, måten feil er inkorporert på og mer.
Selvfølgelig er det alltid mulig at noen vil finne en fatal feil i gitterkryptografi, akkurat som Shor gjorde for factoring. Det er ingen garanti for at et bestemt kryptografisk opplegg vil fungere i møte med ethvert mulig angrep. Kryptografi fungerer til det er sprukket. Faktisk tidligere i sommer en lovende post-kvantekrypteringsordning ble knekt bruker ikke en kvantedatamaskin, men en vanlig bærbar PC. For Stange skaper hele prosjektet et ubehagelig paradoks: "Det jeg synes er så utrolig med kryptografi er at vi har bygget denne infrastrukturen for menneskeheten på den faste troen på at vår evne som mennesker er begrenset," sa hun. "Det er så baklengs."
*: Svaret, hvis du er nysgjerrig, er 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [tilbake til artikkelen]
