1978 Kryptosystem modstår kvanteangreb

Ingen har bygget en kvantecomputer meget mere kraftfuld end en lommeregner, men det har ikke stoppet folk fra at bekymre sig om implikationerne af post-kvantecomputerverdenen. Mest bekymrede er de mennesker, der er afhængige af kryptografiske koder for at beskytte følsomme oplysninger. Når den første kvantecomputer af anstændig størrelse tændes, vil tidligere sikre koder, såsom den almindeligt anvendte RSA-algoritme, blive øjeblikkeligt brudbare.

Det er grunden til, at kryptografer skynder sig om at lede efter koder, der vil være sikre i post-kvanteverdenen. I dag viser Hang Dinh ved University of Connecticut og et par venner, at kryptografer hele tiden har stirret på én. De siger, at en lidt brugt kode udviklet af CalTech-matematikeren Robert McEliece i 1978 kan modstå alle kendte angreb fra kvantecomputere.

Lad os først skelne mellem symmetriske og asymmetriske koder. Symmetriske koder bruger identiske nøgler til at kryptere og dekryptere en besked. Kvantecomputere kan dramatisk fremskynde et angreb mod denne slags koder. Symmetriske koder har dog en vis beskyttelse. En fordobling af nøglens størrelse modvirker denne hastighed. Så det er muligt for kodemagere at være på forkant med bryderne, i hvert fald i teorien. (Selvom de sikre penge i praksis ville være på rovdyret i dette kat og mus-spil.)

Asymmetriske koder bruger forskellige nøgler til at kryptere og dekryptere beskeder. I såkaldte offentlige nøglekrypteringssystemer som den populære RSA-algoritme er en offentlig nøgle tilgængelig for alle, der kan bruge den til at kryptere en besked. Men kun dem med en privat nøgle kan dekryptere beskederne, og dette holdes selvfølgelig hemmeligt.

Sikkerheden i disse systemer er afhængig af såkaldte falddørsfunktioner: matematiske trin, der er nemme at lave i den ene retning, men svære at udføre i den anden. Det mest berømte eksempel er multiplikation. Det er nemt at gange to tal sammen for at få et tredje, men svært at starte med det tredje tal og regne ud, hvilke to der har genereret det, en proces kaldet faktorisering.

Men i 1994 drømte matematikeren Peter Shor om en kvantealgoritme, der kunne faktorisere meget hurtigere end nogen klassisk pendant. En sådan algoritme, der kører på en anstændig kvantecomputer, kunne bryde alle kendte offentlige nøglekrypteringssystemer som en 4-årig, der løber amok i Legoland.

Her er en fornemmelse af, hvordan det fungerer. Problemet med faktorisering er at finde et tal, der deler sig nøjagtigt i et andet. Matematikere gør dette ved at bruge ideen om periodicitet: et matematisk objekt med nøjagtig den rigtige periodicitet skal dividere tallet nøjagtigt, andre vil ikke.

En måde at studere periodicitet i den klassiske verden er at bruge fourier-analyse, som kan nedbryde et signal i dets komponentbølger. Kvanteanalogen til dette er kvante-fourier-samplingen, og Shors triumf var at finde en måde at bruge denne idé til at finde periodiciteten af ​​det matematiske objekt, der afslører faktorerne.

Takket være Shor kan enhver kode, der er afhængig af denne form for asymmetri (dvs. næsten alle populære offentlige nøglekrypteringssystemer) knækkes ved hjælp af et kvante-fourier-angreb.

McEliese-kryptosystemet er anderledes. Det er også asymmetrisk, men dets sikkerhed er ikke baseret på faktorisering, men på en version af en gåde, som matematikere kalder det skjulte undergruppeproblem. Hvad Dinh og venner har vist er, at dette problem ikke kan løses ved hjælp af kvantefourier-analyse. Med andre ord er den immun over for angreb fra Shors algoritme. Faktisk er den immun over for ethvert angreb baseret på kvante-fourier-prøvetagning.

Det er en stor ting. Det betyder, at alt, der er kodet på denne måde, vil være sikkert, når den næste generation af kvantecomputere begynder at tære på de mere konventionelle offentlige nøglekryptosystemer. Et sådant system er Entropy, et peer-to-peer-kommunikationsnetværk designet til at modstå censur baseret på McEliese-kryptosystemet.

Men Entropy er lidt brugt, og der er gode grunde til, at andre har modstået McEliese-krypteringssystemet. Hovedproblemet er, at både de offentlige og private nøgler er noget uhåndterlige: en standard offentlig nøgle er en stor matrix beskrevet af ikke færre end 2^19 bit.

Det kan virke mindre af et problem nu. Det er muligt, at McEleise-systemet pludselig bliver i fokus for meget mere opmærksomhed mere end 30 år efter dets opfindelse.

Det er dog værd at påpege, at mens det nye arbejde garanterer sikkerhed mod alle kendte kvanteangreb, gør det intet af den slags for fremtidige kvanteangreb. Det er helt muligt, at nogen vil udvikle en kvantealgoritme, der vil rive den fra hinanden lige så let, som Shor kan med RSA-algoritmen. Vores resultater udelukker ikke andre kvante- (eller klassiske) angreb, siger Dinh og co.

Så det mere sandsynlige scenarie for fremtidig forskning er, at krytpografer vil forny deres indsats i en af ​​de flere andre retninger, der ser frugtbare ud, såsom gitterbaserede algoritmer og multivariat kryptografi.

Uanset hvad, forvent at høre meget mere om postkvantekryptografi - forudsat at de beføjelser, der tillader det.

Ref: arxiv.org/abs/1008.2390 : McEliece Cryptosystem modstår Quantum Fourier Sampling Angreb

skjule