Een quantumcomputer met een miljoen qubits zou het veelgebruikte RSA-encryptie-algoritme kunnen kraken.
Quantumcomputers zouden een heel gangbare data-encryptietechniek kunnen kraken zodra ze een miljoen quantumbits, of qubits, bevatten. Hoewel dat ruim buiten het bereik van bestaande quantumcomputers ligt, is deze nieuwe schatting wel twintig keer lager dan eerdere. Dat wijst erop dat het moment waarop encryptie wordt gekraakt dichterbij is dan gedacht.
Toegang tot staatsgeheimen
Het veelgebruikte RSA-algoritme werkt doordat het makkelijk is om twee priemgetallen met elkaar te vermenigvuldigen om een grote encryptiesleutel te genereren, terwijl het extreem moeilijk is om de twee oorspronkelijke priemgetallen te bepalen als je enkel over zo’n sleutel beschikt. Maar het is al geruime tijd bekend dat quantumcomputers bepaalde taken die voor klassieke computers erg moeilijk zijn gemakkelijk kunnen uitvoeren – zoals het kraken van RSA-sleutels. Een techniek om dat te bewerkstelligen, Shors algoritme, werd ontwikkeld in 1994.
‘Laat websites en TikTok-filmpjes niet verloren gaan’
We moeten het internet zorgvuldiger archiveren, stelt mediahistoricus Sus ...
Craig Gidney van Google Quantum AI was een van de auteurs van een in 2019 verschenen wetenschappelijk artikel waarin werd geschat dat een quantumcomputer van 20 miljoen qubits in acht uur tijd een RSA-sleutel van een gebruikelijk formaat – 2048 bits – zou kunnen kraken.
Dat zou de gebruiker van zo’n machine in feite in staat stellen om in te breken in elk mailadres of elke bankrekening die beschermd is met deze technologie. Hij of zij zou zo zelfs toegang kunnen krijgen tot staatsgeheimen. Nu heeft Gidney zijn methode geperfectioneerd, waarmee hij het vereiste formaat heeft kunnen terugbrengen tot minder dan een miljoen qubits.
Het laatste laaghangend fruit?
Natuurkundige Peter Leek van de Universiteit van Oxford zegt dat Gidney een grote naam is in het vakgebied en dat zijn nieuwe artikel, dat collega’s nog moeten beoordelen, een boel zal losmaken. Maar hij verwacht ook dat dit het laatste laaghangende fruit is wat betreft het efficiënter maken van Shors algoritme.
‘Het aantal qubits is lager en lager geworden in de loop der decennia, maar het is nog steeds een imposant aantal’, zegt Leek. ‘Het is mogelijk dat mensen het algoritme nóg efficiënter weten te krijgen, maar ik vermoed dat de stapjes kleiner gaan worden.’
Volgende generatie
‘Dit is een goede herinnering dat we richting post-quantumcryptografie moeten blijven bewegen’, zegt cryptograaf Dustin Moody van het Nationale Instituut voor Standaarden en Technologie (NIST). ‘Dit nieuwe onderzoek verandert onze aangekondigde migratietijdlijnen niet, maar we houden alles in de gaten en zullen die aanpassen als dat nodig is.’
NIST heeft de volgende generatie encryptie-algoritmen geselecteerd, die zelfs een quantumcomputer niet zou moeten kunnen kraken. ‘Overheid en industrie zijn al bezig met deze transitie’, zegt Moody.
Van quantumalgoritme naar quantumcircuit
Natuurkundige Aleks Kissinger, net als Leek van de Universiteit van Oxford, zegt dat Gidneys werk niet gebruikmaakt van een fundamenteel nieuwe theorie. Zijn vooruitgang is het gevolg van het combineren van verschillende stappen die de afgelopen zes jaar zijn gezet rond het compileren van quantumalgoritmen naar fysieke quantumcircuits. Een deel van de afname in het aantal qubits is bereikt door de rekentijd te verlengen. Die is gestegen van acht uur in het artikel uit 2019 naar ‘minder dan een week’.
‘Er is een hele parameterruimte die je kunt verkennen, en Gidney heeft waarschijnlijk een van de meest overtuigende combinaties van ruimte (aantal qubits) en (reken)tijd gevonden, waarbij beide er heel redelijk uitzien’, zegt Kissinger. ‘Stel je voor dat het over je eigen computer gaat. Als je meer geheugen hebt, kun je de taken verdelen en van alles parallel doen. Als je minder ruimte hebt om mee te werken, duurt het langer.’
Efficiëntere foutencorrectie
RSA heeft wel als voordeel dat quantumcomputers nog lang niet aan Gidneys vereisten voldoen; het huidige record is net iets meer dan duizend qubits. Maar Leek zegt dat verbeteringen op het gebied van het aantal fouten dat quantumcomputers maken de vereiste van een miljoen qubits nog verder kunnen laten dalen.
‘Ik denk niet dat [het kraken van RSA] zal gebeuren op de manier die dit artikel beschrijft’, zegt Leek. ‘Ik verwacht dat dit gebeurt op een apparaat dat geen miljoen fysieke qubits heeft, maar een innovatievere manier heeft om de foutencorrectie te doen, die efficiënter is geïmplementeerd. Je hoeft maar een factor vier of vijf omlaag om dat resultaat te bereiken, dus dat is heel haalbaar.’
