211service.com
1978 Kryptosystem motstår Quantum Attack
Ingen har byggt en kvantdator som är mycket kraftfullare än en fickkalkylator, men det har inte hindrat människor från att oroa sig för konsekvenserna av postkvantberäkningsvärlden. Mest oroliga är de människor som förlitar sig på kryptografiska koder för att skydda känslig information. När den första kvantdatorn av anständig storlek slås på, kommer tidigare säkra koder som den vanliga RSA-algoritmen att bli omedelbart brytbara.
Vilket är anledningen till att kryptografer skyndar på att leta efter koder som kommer att vara säkra i postkvantvärlden. Idag visar Hang Dinh vid University of Connecticut och ett par kompisar att kryptografer har stirrat på en hela tiden. De säger att en lite använd kod utvecklad av CalTech-matematikern Robert McEliece 1978 kan motstå alla kända attacker från kvantdatorer.
Låt oss först göra en skillnad mellan symmetriska och asymmetriska koder. Symmetriska koder använder identiska nycklar för att kryptera och dekryptera ett meddelande. Kvantdatorer kan dramatiskt påskynda en attack mot dessa typer av koder. Symmetriska koder har dock ett visst skydd. Fördubbling av storleken på nyckeln motverkar denna hastighet. Så det är möjligt för kodskapare att ligga före brytarna, åtminstone i teorin. (Även om de säkra pengarna i praktiken skulle ligga på rovdjuret i detta katt- och råttaspel.)
Asymmetriska koder använder olika nycklar för att kryptera och dekryptera meddelanden. I så kallade public key-krypteringssystem som den populära RSA-algoritmen är en publik nyckel tillgänglig för alla som kan använda den för att kryptera ett meddelande. Men bara de med en privat nyckel kan dekryptera meddelandena och detta hålls naturligtvis hemligt.
Säkerheten i dessa system bygger på så kallade falldörrsfunktioner: matematiska steg som är lätta att göra åt ena hållet men svåra att göra åt andra hållet. Det mest kända exemplet är multiplikation. Det är lätt att multiplicera två tal tillsammans för att få ett tredje men svårt att börja med det tredje talet och räkna ut vilka två som genererade det, en process som kallas faktorisering.
Men 1994 drömde matematikern Peter Shor fram en kvantalgoritm som kunde faktorisera mycket snabbare än någon klassisk motsvarighet. En sådan algoritm som körs på en anständig kvantdator skulle kunna bryta alla kända krypteringssystem för offentliga nyckel som en 4-åring som löper amok i Legoland.
Här är en känsla av hur det fungerar. Problemet med faktorisering är att hitta ett tal som delar sig exakt i ett annat. Matematiker gör detta med hjälp av idén om periodicitet: ett matematiskt objekt med exakt rätt periodicitet ska dela talet exakt, andra gör det inte.
Ett sätt att studera periodicitet i den klassiska världen är att använda fourieranalys, som kan bryta ner en signal i dess komponentvågor. Kvantanalogen till detta är quantum fourier-samplingen och Shors triumf var att hitta ett sätt att använda denna idé för att hitta periodiciteten för det matematiska objektet som avslöjar faktorerna.
Tack vare Shor kan vilken kod som helst som förlitar sig på denna typ av asymmetri (dvs nästan alla populära krypteringssystem för offentliga nyckel) knäckas med hjälp av en quantum fourier-attack.
McElieses kryptosystem är annorlunda. Den är också asymmetrisk men dess säkerhet bygger inte på faktorisering utan på en version av en gåta som matematiker kallar det dolda undergruppsproblemet. Vad Dinh och kompisar har visat är att detta problem inte kan lösas med hjälp av kvantfourieranalys. Med andra ord är den immun mot attacker från Shors algoritm. Faktum är att den är immun mot alla attacker baserat på kvantfourierprovtagning.
Det är en stor sak. Det betyder att allt som är kodat på det här sättet kommer att vara säkert när nästa generation kvantdatorer börjar tjata på de mer konventionella kryptosystemen med publik nyckel. Ett sådant system är Entropy, ett peer-to-peer-kommunikationsnätverk utformat för att motstå censur baserat på McEliese-kryptosystemet.
Men Entropy används lite och det finns goda skäl till varför andra har gjort motstånd mot McEliese-krypteringssystemet. Huvudproblemet är att både de offentliga och privata nycklarna är något svårhanterliga: en vanlig offentlig nyckel är en stor matris som beskrivs av inte mindre än 2^19 bitar.
Det kan tyckas vara ett mindre problem nu. Det är möjligt att McEleise-systemet plötsligt kommer att bli i fokus för mycket mer uppmärksamhet mer än 30 år efter dess uppfinning.
Det är dock värt att påpeka att även om det nya verket garanterar säkerhet mot alla kända kvantattacker, gör det inget sådant för framtida kvantattacker. Det är fullt möjligt att någon kommer att utveckla en kvantalgoritm som kommer att slita isär den lika lätt som Shor kan med RSA-algoritmen. Våra resultat utesluter inte andra kvantattacker (eller klassiska) attacker, säger Dinh och co.
Så det mer sannolika scenariot för framtida forskning är att krytpografer kommer att förnya sina ansträngningar i en av de många andra riktningarna som ser fruktbara ut, såsom gitterbaserade algoritmer och multivariat kryptografi.
Hur som helst, förvänta dig att höra mycket mer om postkvantkryptografi - förutsatt att de befogenheter som är tillåtna.
Ref: arxiv.org/abs/1008.2390 : McEliece-kryptosystemet motstår Quantum Fourier-samplingsattacker