1978 Cryptosysteem weerstaat kwantumaanval

Niemand heeft een kwantumcomputer gebouwd die veel krachtiger is dan een zakrekenmachine, maar dat weerhoudt mensen er niet van zich zorgen te maken over de implicaties van de post-kwantumcomputerwereld. Het meest bezorgd zijn de mensen die vertrouwen op cryptografische codes om gevoelige informatie te beschermen. Wanneer de eerste kwantumcomputer van behoorlijk formaat wordt aangezet, zijn voorheen beveiligde codes, zoals het veelgebruikte RSA-algoritme, direct breekbaar.

Dat is de reden waarom cryptografen haastig op zoek zijn naar codes die veilig zullen zijn in de post-kwantumwereld. Vandaag laten Hang Dinh van de Universiteit van Connecticut en een paar vrienden zien dat cryptografen er al die tijd naar hebben gestaard. Ze zeggen dat een weinig gebruikte code, ontwikkeld door de CalTech-wiskundige Robert McEliece in 1978, alle bekende aanvallen van kwantumcomputers kan weerstaan.

Laten we eerst een onderscheid maken tussen symmetrische en asymmetrische codes. Symmetrische codes gebruiken identieke sleutels voor het versleutelen en ontsleutelen van een bericht. Quantumcomputers kunnen een aanval op dit soort codes drastisch versnellen. Symmetrische codes hebben echter enige bescherming. Een verdubbeling van de grootte van de sleutel gaat deze snelheid tegen. Het is dus mogelijk voor codemakers om de breakers voor te blijven, althans in theorie. (Hoewel in de praktijk het veilige geld op het roofdier zou zijn in dit kat-en-muisspel.)

Asymmetrische codes gebruiken verschillende sleutels voor het versleutelen en ontsleutelen van berichten. In zogenaamde public key-encryptiesystemen, zoals het populaire RSA-algoritme, is een publieke sleutel beschikbaar voor iedereen die deze kan gebruiken om een ​​bericht te versleutelen. Maar alleen degenen met een privésleutel kunnen de berichten ontsleutelen en dit wordt natuurlijk geheim gehouden.

De beveiliging van deze systemen berust op zogenaamde valdeurfuncties: wiskundige stappen die in de ene richting gemakkelijk te maken zijn, maar in de andere moeilijk uit te voeren. Het bekendste voorbeeld is vermenigvuldiging. Het is gemakkelijk om twee getallen met elkaar te vermenigvuldigen om een ​​derde te krijgen, maar het is moeilijk om met het derde getal te beginnen en uit te zoeken welke twee het hebben gegenereerd, een proces dat factorisatie wordt genoemd.

Maar in 1994 bedacht de wiskundige Peter Shor een kwantumalgoritme dat veel sneller kon ontbinden dan welke klassieke tegenhanger dan ook. Zo'n algoritme dat op een degelijke kwantumcomputer draait, zou alle bekende versleutelingssystemen met openbare sleutels kunnen breken, zoals een 4-jarige die op hol slaat in Legoland.

Hier is een idee van hoe het werkt. Het probleem van factorisatie is om een ​​getal te vinden dat precies in een ander deelbaar is. Wiskundigen doen dit met het idee van periodiciteit: een wiskundig object met precies de juiste periodiciteit zou het getal exact moeten delen, andere niet.

Een manier om periodiciteit in de klassieke wereld te bestuderen, is door Fourier-analyse te gebruiken, die een signaal kan opsplitsen in zijn samenstellende golven. De kwantumanaloog hiervoor is de kwantum-fourier-bemonstering en Shor's triomf was om een ​​manier te vinden om dit idee te gebruiken om de periodiciteit te vinden van het wiskundige object dat de factoren onthult.

Dankzij Shor kan elke code die afhankelijk is van dit soort asymmetrie (dwz bijna alle populaire versleutelingssystemen met openbare sleutels) worden gekraakt met behulp van een kwantum-fourier-aanval.

Het McEliese cryptosysteem is anders. Het is ook asymmetrisch, maar de beveiliging ervan is niet gebaseerd op factorisatie, maar op een versie van een raadsel dat wiskundigen het verborgen supgroup-probleem noemen. Wat Dinh en vrienden hebben aangetoond, is dat dit probleem niet kan worden opgelost met behulp van kwantum-fourieranalyse. Met andere woorden, het is immuun voor aanvallen door het algoritme van Shor. In feite is het immuun voor elke aanval op basis van quantum fourier-bemonstering.

Dat is een groot probleem. Het betekent dat alles dat op deze manier is gecodeerd, veilig zal zijn wanneer de volgende generatie kwantumcomputers begint te kauwen op de meer conventionele cryptosystemen met openbare sleutels. Een zo'n systeem is Entropy, een peer-to-peer communicatienetwerk dat is ontworpen om censuur te weerstaan ​​op basis van het McEliese-cryptosysteem.

Maar Entropy wordt weinig gebruikt en er zijn goede redenen waarom anderen weerstand hebben geboden aan het McEliese-coderingssysteem. Het grootste probleem is dat zowel de openbare als de privésleutel nogal onpraktisch zijn: een standaard openbare sleutel is een grote matrix die wordt beschreven door niet minder dan 2^19 bits.

Dat lijkt nu misschien minder een probleem. Het is mogelijk dat het McEleise-systeem meer dan 30 jaar na zijn uitvinding plotseling veel meer aandacht krijgt.

Het is echter de moeite waard om erop te wijzen dat hoewel het nieuwe werk de veiligheid tegen alle bekende kwantumaanvallen garandeert, het niets van dien aard is voor toekomstige kwantumaanvallen. Het is heel goed mogelijk dat iemand een kwantumalgoritme ontwikkelt dat het zo gemakkelijk uit elkaar haalt als Shor kan met het RSA-algoritme. Onze resultaten sluiten andere kwantum- (of klassieke) aanvallen niet uit, zeggen Dinh en co.

Het meest waarschijnlijke scenario voor toekomstig onderzoek is dat crytpografen hun inspanningen zullen hernieuwen in een van de verschillende andere richtingen die vruchtbaar lijken, zoals roostergebaseerde algoritmen en multivariate cryptografie.

Hoe dan ook, verwacht nog veel meer te horen over post-kwantumcryptografie, mits de bevoegdheden die zijn toegestaan.

Referentie: arxiv.org/abs/1008.2390 : Het McEliece Cryptosystem weerstaat Quantum Fourier Sampling-aanvallen

zich verstoppen