Op 23 oktober 2019 kondigde Google aan dat hun kwantumprocessor Sycamore erin was geslaagd om in 3 minuten een probleem op te lossen waarvoor meer dan 10.000 jaar rekenwerk nodig zou zijn geweest voor een supercomputer. Het was het eerste verklaarde geval van kwantumsuprematie.
Deze technologie belooft op veel gebieden mogelijkheden te openen. Het vormt echter ook een nieuw risico voor de moderne cryptografie, waarvan de beveiliging gebaseerd is op wiskundige problemen die moeilijk op te lossen zijn. Wat gebeurt er als deze rekenmoeilijkheid niet langer een obstakel vormt?
In deze nieuwe serie artikelen onderzoeken we het potentieel van kwantumcomputing en analyseren we de mogelijke effecten ervan op Bitcoin.
Wat is een kwantumcomputer?
Tijdens het doorbladeren van dit artikel gebruik je waarschijnlijk een gewone computer of misschien een smartphone. Deze apparaten kunnen rekenbewerkingen uitvoeren, hoewel ze beperkingen hebben. Bij bepaalde complexe berekeningen zou de machine inderdaad miljoenen jaren moeten draaien voordat er een oplossing kon worden gevonden. Het voordeel van een kwantumcomputer is dat deze bepaalde specifieke berekeningen veel sneller kan uitvoeren dan een klassieke computer.
Om dit resultaat te bereiken heeft de werking van de kwantumcomputer absoluut niets te maken met de werking van de klassieke computer. De traditionele computer manipuleert bits die twee verschillende toestanden kunnen bevatten: 0 of 1 — en die gecombineerd worden om code te maken en taken uit te voeren. Klassiek computergebruik is daarom gebaseerd op de fundamentele principes van elektriciteit, terwijl kwantumcomputing gebaseerd is op de principes van de kwantumfysica.
In plaats van informatie met bits te verwerken, gebruiken kwantumcomputers kwantumbits, ook wel „qubits” genoemd. Deze qubits kunnen 0 of 1 zijn, of een superpositie van 0 en 1. Door deze superpositie van toestanden te gebruiken met andere kwantumfenomenen zoals verstrengeling en kwantuminterferentie, kan een kwantumcomputer berekeningstaken parallelliseren en daardoor bepaalde problemen veel sneller oplossen.
De uitdaging ligt in het feit dat cryptografie gebaseerd is op wiskundige problemen die door traditionele computers als onoplosbaar worden beschouwd. Het is echter mogelijk dat deze wiskundige problemen in de toekomst binnen een aanvaardbare tijd kunnen worden opgelost door kwantumcomputers, wat onze huidige cryptografische standaarden zou breken.
Wat zijn de risico's van cryptografie?
Tot op heden zijn er voornamelijk twee kwantumalgoritmen die een bedreiging kunnen vormen voor sommige moderne cryptografische primitieven. Dit zijn de algoritmen van Shor (1994) en Grover (1996).
Het Shor-algoritme is ontworpen om hele getallen in hun priemfactoren in polynomiale tijd te ontleden. Dit houdt in dat de benodigde berekeningstijd op een acceptabele manier toeneemt met de grootte van het getal waarmee rekening moet worden gehouden. De meest efficiënte klassieke algoritmen op dit gebied vertonen daarentegen een complexiteit die wordt beschreven als „sub-exponentieel”.
Enkele van de meest gebruikte cryptografische methoden ter wereld zijn echter precies gebaseerd op dit probleem van het factoreren van grote gehele getallen. Dit is bijvoorbeeld het geval bij het RSA-algoritme.
Simpel gezegd, als traditionele computers erin slagen het RSA-cijfer te doorbreken, is het mogelijk om de beveiliging van het algoritme te herstellen door de gebruikte sleutels te vergroten. We zijn dan even stil, aangezien de complexiteit subexponentieel toeneemt met de grootte van de sleutel. Door het gebruik van het kwantumalgoritme van Shor neemt deze complexiteit echter veel minder snel toe, wat uiteindelijk het veilige gebruik van versleutelingsmethoden zoals RSA in gevaar zou kunnen brengen.
Dit Shor-algoritme kan worden aangepast om ook het probleem van de discrete logaritme in polynomiale tijd aan te pakken. Dit is het wiskundige probleem dat wordt gebruikt in de context van Diffie-Hellman of cryptografie op elliptische krommen.
Het Grover-algoritme kan daarentegen worden gebruikt om ongestructureerde zoekproblemen op te lossen. Met andere woorden, het is ontworpen om naar een specifiek item te zoeken in een ongeorganiseerde database, en het doet dit veel sneller dan een conventioneel algoritme zou doen. Het kan met name nuttig zijn om botsingen op een hash-functie te vinden.
Grover en Shor zijn twee algoritmen die sommige moderne cryptografische primitieven zouden kunnen ondermijnen. Maar hoewel ze al heel lang bestaan, is het tot op heden nog steeds onmogelijk om ze op een kwantumcomputer uit te voeren.
De redenen voor deze onmogelijkheid zijn talrijk. Allereerst zouden we een kwantumcomputer moeten hebben met een zeer groot aantal qubits. Dan zouden deze qubits een minimaal foutenpercentage moeten hebben. Foutcorrectietechnieken zijn op dit moment echter nog in ontwikkeling. Ten slotte moeten qubits hun kwantumtoestand lang genoeg kunnen behouden om dergelijke complexe berekeningen uit te voeren. De huidige tijden zijn te kort en de informatie gaat verloren voordat alle vereiste handelingen kunnen worden uitgevoerd.
Op korte en middellange termijn lijkt er dus geen bedreiging te zijn voor crypto. Dat is in ieder geval naar voren gekomen uit de adviezen van experts, zoals blijkt uit een EvolutionQ-enquête die in 2022 werd uitgevoerd onder 40 professionals in de sector.
In dit onderzoek werd hen gevraagd hoe groot de kans was dat een kwantumcomputer in 24 uur een RSA-sleutel van 2.048 bits zou kunnen breken, vergeleken met verschillende tijdshorizonten vanaf het jaar 2022. Binnen 5 jaar schat een enkele expert dat er een kans van meer dan 50% is dat de beschreven situatie zich zal voordoen. Binnen 15 jaar is meer dan de helft van de experts van mening dat de kans groter is dan 50%. Op 30-jarige leeftijd is bijna iedereen het daarmee eens, en bijna een derde gelooft zelfs dat er een kans van 99% is dat een RSA-sleutel wordt verbroken.
Krediet: globalriskinstitute.org
Uit dit onderzoek blijkt dat experts zich op korte en middellange termijn weinig zorgen maken over de bedreigingen die quantum computing zou kunnen vormen voor cryptografie. Aan de andere kant zijn ze op de lange termijn veel pessimistischer.
Conclusie
In dit eerste hoofdstuk ontdekte je waarom quantum computing een risico vormt voor cryptografie. De belangrijkste bedreigingen zijn de algoritmen van Shor en Grover. We zijn echter nog lang niet in staat om ze succesvol uit te voeren op een machine. Dit is simpelweg te wijten aan het feit dat we nog geen kwantumcomputer hebben die voldoende stabiel en krachtig is.
Volgens deskundigen in deze sector moet deze dreiging serieus worden genomen. Het is echter een risico dat zich gedurende meerdere jaren of zelfs decennia niet zou moeten voordoen.
In het tweede hoofdstuk van deze serie zullen we meer specifiek kijken naar de risico's die op het Bitcoin-protocol wegen. We zullen zien of kwantumcomputers invloed kunnen hebben op de uitvinding van Satoshi Nakamoto.
.png)
