Introduktion
I 1994 skrev datalogen Peter Shor opdaget at hvis kvantecomputere nogensinde blev opfundet, ville de ødelægge meget af den infrastruktur, der blev brugt til at beskytte information, der deles online. Den skræmmende mulighed har fået forskere til at kæmpe for at producere nye, "post-kvante" krypteringssystemer, for at redde så meget information, som de kunne, fra at falde i hænderne på kvantehackere.
Tidligere i år, National Institute of Standards and Technology afslørede fire finalister i sin søgen efter en post-kvantekryptografistandard. Tre af dem bruger "gitterkryptografi" - et skema inspireret af gitter, regelmæssige arrangementer af prikker i rummet.
Gitterkryptografi og andre post-kvante muligheder adskiller sig fra de nuværende standarder på afgørende måder. Men de er alle afhængige af matematisk asymmetri. Sikkerheden i mange nuværende kryptografisystemer er baseret på multiplikation og factoring: Enhver computer kan hurtigt gange to tal, men det kan tage århundreder at indregne et kryptografisk stort tal i dets primære bestanddele. Den asymmetri gør hemmeligheder nemme at kode, men svære at afkode.
Hvad Shor afslørede i sin algoritme fra 1994 var, at et særpræg ved factoring gør det sårbart over for angreb fra kvantecomputere. "Det er en meget specifik, speciel ting, som kvantecomputeren kan," sagde Katherine Stange, en matematiker ved University of Colorado, Boulder. Så efter Shor havde kryptografer et nyt job: Find et nyt sæt matematiske operationer, der er lette at udføre, men næsten umulige at fortryde.
Gitterkryptering er et af de hidtil mest succesfulde forsøg. Oprindeligt udviklet i 1990'erne, er det afhængigt af vanskeligheden ved omvendt konstruktion af pointsummer.
Her er en måde at beskrive gitterkryptografi på: Forestil dig, at din ven har et gitter, som blot er en masse punkter i et regulært, gentaget mønster over hele flyet. Din ven vil have dig til at nævne 10 af disse punkter. Men han har det svært, og han vil ikke tegne hele gitteret. I stedet opregner han kun to punkter - det første med en x-værdi af 101 og en y-værdi på 19, den anden med koordinater [235, 44].
Heldigvis er det nemt at finde nye punkter på et gitter, for når du tilføjer og trækker to punkter fra et gitter, får du et tredje punkt i det samme gitter. Så alt du skal gøre er at lægge de point sammen, som din ven gav dig, eller gange dem med heltal og derefter lægge dem sammen, eller en kombination af de to. Gør dette på otte forskellige måder, og du vil være i stand til at besvare din vens spørgsmål.
Men din ven er stadig ikke tilfreds. Han giver dig de samme to udgangspunkter, og spørger dig derefter, om punktet [2, 1] er på det samme gitter. For at besvare dette spørgsmål korrekt, skal du finde kombinationen af [101, 19] og [235, 44], der giver [2, 1]. Dette problem er meget sværere end det første, og du ender sandsynligvis med bare at gætte og tjekke for at få svaret.* Den asymmetri er det, der ligger til grund for gitterkryptografi.
Hvis du rent faktisk vil bruge gitterkryptografi til at dele information, skal du gøre følgende. Forestil dig, at en ven (en bedre en!) vil sende dig en sikker besked. Du starter med et kvadratisk gitter af tal. Lad os sige, at den har to rækker og to kolonner og ser sådan ud:
Nu kommer du med en privat "nøgle", som kun du kender. Lad os i dette eksempel sige, at din private nøgle kun er to hemmelige numre: 3 og -2. Man ganger tallene i første kolonne med 3 og tallene i anden kolonne med −2. Tilføj resultaterne i hver række for at få en tredje kolonne med to poster.
Sæt den nye kolonne fast på enden af dit gitter. Dette nye gitter med tre kolonner er din offentlige nøgle. Del det frit!
(Et scenarie i den virkelige verden vil være lidt mere kompliceret. For at forhindre hackere i at afkode din private nøgle, skal du tilføje en smule tilfældig støj i din sidste kolonne. Men her vil vi ignorere det trin for enkelhedens skyld. )
Nu vil din ven bruge den offentlige nøgle til at sende dig en besked. Hun tænker på to egne hemmelige tal: 2 og 0. Hun multiplicerer tallene i første række med 2, og tallene i anden række med 0. Hun lægger derefter resultaterne sammen i hver kolonne for at få en tredje række.
Hun vedhæfter nu den nye række til bunden af gitteret og sender den tilbage til dig. (Igen, i et rigtigt system, skulle hun tilføje noget støj til sin række.)
Nu vil du læse beskeden. For at gøre dette skal du kontrollere, om din vens sidste række er korrekt. Anvend din egen private nøgle til de to første poster i hendes række. Resultatet skal matche den sidste post.
Din ven kan også vælge at sende dig en række med et forkert nummer i den sidste kolonne. Hun ved, at dette tal ikke stemmer overens med dine beregninger.
Hvis din ven sender en række, hvor det sidste tal er korrekt, tolker du dette som et 0. Hvis hun sender en række, hvor tallet er forkert, tolker du det som et 1. Rækken koder derfor en enkelt bit: enten 0 eller 1.
Bemærk, at en ekstern angriber ikke vil have adgang til hverken din private nøgle eller din vens. Uden disse vil angriberen ikke have nogen idé om, om det endelige tal er korrekt eller ej.
I praksis vil du gerne sende beskeder, der er længere end en smule lange. Så folk, der ønsker at modtage f.eks. en 100-bit besked, vil generere 100 nye kolonner i stedet for kun én. Derefter vil afsenderen af meddelelsen oprette en enkelt ny række og ændre de sidste 100 poster til at kode enten et 0 eller et 1 for hver post.
Hvis gitterkryptografi rent faktisk implementeres, vil den have utallige nuancer, der ikke er dækket af dette scenarie. For eksempel, hvis du ønsker, at meddelelsen virkelig skal være sikker fra nysgerrige øjne, skal matrixen have et utænkeligt antal poster, hvilket gør det hele så uhåndterligt, at det ikke er værd at bruge. For at komme uden om dette bruger forskere matricer med nyttige symmetrier, der kan skære ned på antallet af parametre. Ud over det er der en hel række tweaks, der kan anvendes på selve problemet, på den måde, fejl er inkorporeret på og meget mere.
Selvfølgelig er det altid muligt, at nogen vil finde en fatal fejl i gitterkryptografi, ligesom Shor gjorde for factoring. Der er ingen sikkerhed for, at et bestemt kryptografisk skema vil fungere i lyset af ethvert muligt angreb. Kryptografi virker, indtil det er revnet. Faktisk tidligere på sommeren et lovende post-kvantekryptografiskema blev knækket bruger ikke en kvantecomputer, men en almindelig bærbar. For Stange skaber hele projektet et ubehageligt paradoks: "Det, jeg finder så fantastisk ved kryptografi, er, at vi har bygget denne infrastruktur til menneskeheden ud fra den faste overbevisning om, at vores evner som mennesker er begrænsede," sagde hun. "Det er så baglæns."
*: Svaret, hvis du er nysgerrig, er 7 × [101, 19] – 3 × [235, 44] = [2, 1]. [tilbage til artiklen]
