Amazon-onderzoeker claimt kwantumdoorbraak die postkwantumcrypto kan raken

Daniel R. Simon, cryptograaf bij de Cryptography Group van Amazon Web Services, publiceerde deze week een preliminair paper met een opvallende claim: hij zou een kwantumalgoritme hebben gevonden dat het zogeheten Dihedral Coset Problem (DCP) in polynomiale tijd oplost. Dat wiskundige probleem houdt onderzoekers al meer dan twintig jaar bezig, omdat eerder werk het verbond aan een reeks lastige roosterproblemen die aan de basis staan van roostergebaseerde cryptografie. Die vorm van versleuteling vormt de ruggengraat van de meeste standaarden voor post-quantum cryptografie die het Amerikaanse standaardisatie-instituut NIST heeft goedgekeurd.

Wat is het Dihedral Coset Problem?

Een rooster is een regelmatig patroon van punten, uitgestrekt over vele dimensies. Cryptografen bouwen daarop puzzels die eenvoudig te maken zijn, maar extreem lastig om te kraken. Twee bekende voorbeelden zijn het Shortest Vector Problem, waarbij een computer de kortste niet-triviale stap in een rooster moet vinden, en Learning With Errors, waarbij informatie verstopt zit in vergelijkingen met opzettelijk toegevoegde ruis. Beide problemen vormen de basis van een groot deel van de huidige post-quantum encryptie. Het DCP is een variant van wat wiskundigen een 'verborgen-subgroepprobleem' noemen: een kwantumcomputer krijgt monsters met twee gerelateerde waarden die een onbekende afstand van elkaar liggen, en moet die verborgen waarde achterhalen. Kwantumcomputers zijn hier van nature goed in - hetzelfde principe ligt ten grondslag aan het beroemde Shors algoritme, waarmee RSA- en elliptische-curve-encryptie in theorie te kraken zijn. Voor het dihedrale geval bleek een efficiënte oplossing echter veel weerbarstiger.

Een ontbrekend puzzelstuk

Wiskundige Oded Regev liet eerder zien dat een efficiënt DCP-algoritme gebruikt zou kunnen worden om ook bepaalde roosterproblemen efficiënt op te lossen. Zijn constructie leunde echter op een 'subset-sum oracle', een theoretisch hulpmiddel dat zelf niet praktisch uitvoerbaar is. Daardoor bleef de doorbraak tot nu toe hypothetisch. De beste eerder bekende kwantumaanpak, van wiskundige Greg Kuperberg, werkte in subexponentiële tijd - sneller dan volledig exponentieel, maar nog altijd niet polynomiaal. Simon claimt nu een polynomiale-tijd procedure te hebben gevonden die zonder het onpraktische orakel werkt. Zijn methode splitst grote hoeveelheden kwantummonsters op in groepen, verwijdert voorzichtig overtollige informatie zonder de cruciale kwantumfase te verstoren, en herhaalt dat proces recursief om bit voor bit de verborgen waarde te achterhalen. Een belangrijk detail is dat het algoritme volgens de paper ook overweg kan met een deel foutieve monsters - tot ongeveer één op de logaritme van de probleemgrootte - wat van belang is omdat de vertaalslag naar roosterproblemen dat soort fouten juist introduceert.

Nog geen reden tot paniek

Concreet claimt de paper dat het algoritme leidt tot polynomiale-tijd kwantumoplossingen voor bepaalde benaderingen van het Shortest Vector Problem en Learning With Errors, met een nauwkeurigheid rond de wortel van de dimensie vermenigvuldigd met een polylogaritmische factor. Dat is een theoretische doorbraak, geen praktische aanval. Het paper berekent niet hoeveel qubits of foutcorrectie een aanvaller nodig zou hebben, en toont geen concrete inbraak op gestandaardiseerde post-quantum systemen. Bovendien is het resultaat nog niet onafhankelijk geverifieerd: de bewijsvoering bevat complexe kansrekening over de verdeling van subset-sommen, en juist dat soort argumenten is gevoelig voor subtiele fouten. Cryptografen wereldwijd zullen de komende maanden de proef nauwkeurig doorlichten voordat conclusies over de veiligheid van bestaande systemen getrokken kunnen worden.