⚛️ quantum physics

On the practicality of quantum sieving algorithms for the shortest vector problem

Deze studie concludeert dat quantum-sieving-algoritmen, zelfs onder zeer optimistische aannames over hardware en foutcorrectie, geen noemenswaardige snelheidswinst bieden voor het oplossen van het kortste-vectorenprobleem in cryptografisch relevante dimensies, aangezien de benodigde tijd en het aantal qubits vergelijkbaar zijn met die van klassieke computers.

Oorspronkelijke auteurs: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

Gepubliceerd 2026-04-13

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, Aditya Morolia

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Grote Quantum-Detective: Waarom de "Snelle" Computer nog niet de Lijst van de Dief kan kraken

Stel je voor dat je een enorme bibliotheek hebt, gevuld met miljarden boeken. Je bent op zoek naar één specifiek boek: het kortste boek in de hele collectie. Dit is een beetje wat de Kortste Vector Probleem (SVP) is in de wereld van cryptografie. Het is de sleutel tot het breken van de beveiliging van onze toekomstige internet-communicatie (post-kwantum cryptografie).

Vandaag de dag zijn er twee soorten detectives die dit boek kunnen zoeken:

De Klassieke Detective: Een slimme mens met een pen en papier (of een supercomputer).
De Quantum-Detective: Een magische, super-snelle zoekmachine die gebruik maakt van de vreemde wetten van de quantumwereld.

Dit paper, geschreven door een team van onderzoekers, stelt de vraag: "Is die Quantum-Detective echt zo snel dat hij onze beveiliging kan kraken?"

Het korte antwoord is: Nee, niet zolang we niet over de technologie van morgen beschikken. Zelfs met de allerbeste, meest optimistische aannames, is de quantum-detective op dit moment net zo traag als de klassieke detective.

Hier is hoe ze tot die conclusie komen, vertaald in alledaagse termen:

1. De Opdracht: Het Naaldje in de Hooiberg vinden

De cryptografische systemen die we willen beschermen, zijn gebaseerd op het vinden van het kortste lijntje in een gigantisch, wiskundig rooster (een "lattice").

De Klassieke methode (Sieving): Stel je voor dat je een berg stenen hebt. Je pakt twee willekeurige stenen, telt ze bij elkaar op en kijkt of het resultaat een kleinere steen is. Als dat zo is, gooi je de grote weg en houd je de kleine. Je herhaalt dit miljoenen keren tot je de kleinste steen overhoudt.
De Quantum-methode: De quantum-detective gebruikt een trucje (de Grover-zoektocht) om sneller te kijken of er een kleinere steen is. In theorie zou hij de berg in de helft van de tijd moeten kunnen doorzoeken.

2. De Grote Valstrik: De "Quantum-Geheugenkast" (QRAM)

Hier wordt het spannend. Om de quantum-detectie te laten werken, moet hij toegang hebben tot een gigantische lijst met stenen. In de quantumwereld heb je daarvoor een speciaal apparaat nodig: een QRAM (Quantum Random Access Memory).

De Analogie: Stel je voor dat de quantum-detectie een magische bril draagt die hem laat zien waar de stenen zijn. Maar om die bril te gebruiken, moet hij eerst een enorme, fysieke kast met miljoenen laden openen.
Het Probleem: Om die kast te bouwen en te bedienen, heb je ontzettend veel quantum-bitjes (qubits) nodig. De onderzoekers berekenden dat voor een veilige cryptografische taak, je een kast nodig hebt die groter is dan het aantal transistors in alle computers ter wereld samen. Je hebt ongeveer 10 tot de 13e macht (10.000.000.000.000) fysieke qubits nodig. Dat is meer dan het aantal zandkorrels op een groot strand.

3. De "Ruis" en de "Reparatie"

Quantum-computers zijn erg kwetsbaar. Ze zijn als een glazen huis in een storm: elke kleine trilling (ruis) kan de boel breken.

Om dit op te lossen, moeten we de qubits "repareren" met een techniek genaamd Foutcorrectie.
De Analogie: Het is alsof je één echte qubit wilt hebben, maar je moet hem beschermen met een schild van 1.000 andere qubits die constant controleren of de echte qubit nog heel is.
Dit maakt de quantum-detectie nog zwaarder. Je hebt niet alleen de kast nodig, maar ook een heel leger van reparateurs die non-stop werken.

4. De Uitslag: Wie wint er?

De onderzoekers hebben alles opgeteld: de tijd, de hoeveelheid hardware, de energie en de foutcorrectie. Ze hebben gekeken naar de dimensie 400, wat de standaard is voor de beveiliging die NIST (de Amerikaanse veiligheidsinstantie) wil invoeren.

Het Resultaat: Zelfs als we aannemen dat we de perfecte quantum-computer hebben (met de allerbeste technologie die we ons nu kunnen voorstellen), duurt het 10 tot de 31e macht jaar om het probleem op te lossen.
Vergelijking: Dat is langer dan de leeftijd van het heelal (ongeveer 13 miljard jaar).
De Klassieke tegenhanger: Een gewone, snelle computer (zoals een moderne server) zou ongeveer even lang doen.

Conclusie: Geen "Quantum-Sprong" voor nu

De paper concludeert dat er voor de cryptografische dimensies die we nu gebruiken, geen echte snelheidswinst is voor quantum-computers.

De boodschap: De "magische" quantum-snelheid wordt volledig opgegeten door de enorme kosten om de hardware te bouwen en te onderhouden.
De toekomst: Om quantum-computers echt gevaarlijk te maken voor deze cryptografie, hebben we niet alleen betere algoritmen nodig, maar een revolutie in hardware. We moeten de "Quantum-Geheugenkast" (QRAM) veel kleiner en goedkoper kunnen maken, en we moeten de "reparateurs" veel efficiënter kunnen laten werken.

Kort samengevat:
De quantum-detective heeft een snellere auto, maar hij zit vast in een gigantische file van verkeerslichten (QRAM-kosten) en moet constant zijn auto laten repareren (foutcorrectie). De klassieke detective rijdt langzaam, maar hij heeft geen file en geen reparaties nodig. Op dit moment komen ze op hetzelfde moment aan bij het doel. Onze cryptografie is dus voorlopig veilig!

Titel: De praktische haalbaarheid van kwantumsievelingsalgoritmen voor het kortste-vectorkprobleem (SVP)

Auteurs: Joao F. Doriguello, George Giapitzakis, Alessandro Luongo, en Aditya Morolia.
Publicatiedatum: Februari 2025.

1. Het Probleem

Lattic-cryptografie is een van de belangrijkste kandidaten voor post-kwantumcryptografie (PQC), met name omdat deze gebaseerd is op de wiskundige moeilijkheid van het Kortste-Vectorkprobleem (SVP). Het SVP vraagt om het vinden van de kortste niet-nul vector in een geheel getallenrooster. De beveiliging van NIST-standaarden (zoals Kyber en Dilithium) hangt af van het feit dat SVP zelfs voor kwantumcomputers onoplosbaar moet blijven binnen redelijke tijd.

Hoewel er asymptotische kwantumsnelheidsverbeteringen bekend zijn voor SVP (voornamelijk door het toepassen van Grover's zoekalgoritme op klassieke sievelingsalgoritmen zoals de Nguyen-Vidijk-sieve en GaussSieve), ontbreekt er een nauwkeurige resource-schatting voor cryptografisch relevante dimensies. Bestaande studies negeren vaak de kosten van Quantum Random Access Memory (QRAM), foutcorrectie en specifieke hardware-architecturen, wat leidt tot optimistische en mogelijk misleidende schattingen.

2. Methodologie

De auteurs voeren een rigoureuze, niet-asymptotische resource-schatting uit voor het implementeren van Grover's zoekalgoritme in verschillende sievelingsalgoritmen. Ze analyseren de kosten voor een roosterdimensie van D = 400 (de dimensie die nodig is om de minimaal veilige NIST-standaarden te breken).

De analyse omvat de volgende kritieke componenten:

Algoritmen: Ze evalueren de Nguyen-Vidijk-sieve (NVSieve) en de GaussSieve, zowel in hun "plaine" vorm als verbeterd met Locality-Sensitive Hashing (LSH) en Locality-Sensitive Filtering (LSF) (zoals Angular LSH, Spherical LSH, en Spherical LSF).
Kwantumrekenkunde: Ze gebruiken vaste-puntarithmetic (32-bit) en modelleren de kosten van optellers, vergelijkers en vermenigvuldigers met behulp van de meest geavanceerde circuits (o.a. Gidney's out-of-place adder).
Grover's Zoekalgoritme: Ze nemen in aanmerking dat het aantal oplossingen vaak onbekend is, wat een exponentiële zoekvariant van Grover vereist.
QRAM: Ze modelleren de kosten van QRAM (specifiek de "bucket-brigade" architectuur), die essentieel is om klassieke data in superpositie te benaderen. Dit is een grote kostenpost in termen van qubits.
Foutcorrectie en Architectuur:
- Ze nemen een realistisch, maar optimistisch, ruismodel aan ( $p_{phy} = 10^{-5}$ ).
- Ze gebruiken Surface Codes voor foutcorrectie.
- Ze vergelijken twee hardware-architecturen: een Baseline-architectuur (2D grid, naburige interacties) en een Active-Volume-architectuur (met niet-lokale connecties, voorgesteld door Litinski en Nickerson).
- Ze houden rekening met Magic State Distillation voor niet-Clifford-gates (Toffoli/CCZ) en de "reaction time" (1 µs) voor klassieke decoding.

3. Belangrijkste Bijdragen

Eerste volledige resource-schatting: Dit is een van de eerste werken dat de totale kosten (tijd en qubits) van kwantumsieveling berekent inclusief QRAM, foutcorrectie en specifieke arithmetische circuits, in plaats van alleen te kijken naar het aantal logische operaties.
Integratie van QRAM-kosten: De auteurs tonen aan dat QRAM de dominante factor is in het aantal benodigde fysieke qubits, omdat de grootte van het geheugen lineair schaalt met de grootte van de database die wordt doorzocht.
Vergelijking Klassiek vs. Kwantum: Ze vergelijken de kwantumsnelheid niet alleen met klassieke asymptotische complexiteit, maar met de feitelijke uitvoeringstijd van een klassieke single-core computer (6 GHz).
Analyse van Hashing-technieken: Ze evalueren hoe LSH/LSF de resource-eisen beïnvloeden, waarbij ze aantonen dat hoewel deze technieken de zoekruimte verkleinen, de QRAM-kosten en de klassieke voorverwerkingstijd de voordelen beperken.

4. Resultaten

De resultaten zijn overwegend pessimistisch voor de praktische haalbaarheid van kwantum-aanvallen op huidige PQC-standaarden:

Aantal Qubits: Voor een rooster van dimensie D = 400 vereist de beste kwantumsieveling (GaussSieve met Spherical LSF) onder een Active-Volume-architectuur ongeveer $10^{13}$ fysieke qubits. Dit is meerdere ordes van grootte meer dan het aantal transistors in moderne supercomputers.
Uitvoeringstijd: De geschatte tijd om SVP op te lossen is ongeveer $10^{31}$ jaar.
Vergelijking met Klassiek: Een enkele klassieke single-core computer (6 GHz) zou ongeveer dezelfde tijd ( $10^{31}$ jaar) nodig hebben om hetzelfde probleem op te lossen. Er is dus geen significant kwantumvoordeel op cryptografisch relevante dimensies.
Invloed van QRAM: Als men de kosten van QRAM negeert (wat onrealistisch is), daalt het aantal qubits drastisch (naar $10^9$ ), maar de uitvoeringstijd blijft enorm door de diepte van de circuits en de noodzaak van foutcorrectie.
NIST Dieptbeperkingen: Zelfs als men de circuitdiepte beperkt tot de door NIST voorgestelde maximumwaarden ( $2^{40}$ tot $2^{96}$ ), neemt de tijd om het probleem op te lossen exponentieel toe, terwijl het aantal qubits slechts beperkt daalt.

5. Betekenis en Conclusie

Het artikel concludeert dat er op dit moment weinig tot geen kwantumsnelheidsverbetering is voor het oplossen van SVP in de dimensies die relevant zijn voor post-kwantumcryptografie.

Geen bedreiging op korte termijn: De huidige theoretische kwantumalgoritmen (zoals Grover's zoekopdracht op sieves) vereisen hardware die ver buiten het bereik ligt van wat er in de nabije toekomst mogelijk is (miljarden qubits en extreme stabiliteit).
QRAM als knelpunt: De noodzaak van QRAM is de grootste barrière. Zonder een doorbraak in de efficiëntie van QRAM-architecturen of een fundamenteel nieuwe theoretische aanpak, zullen kwantumcomputers geen bedreiging vormen voor lattice-based cryptografie.
Toekomstperspectief: Any aanzienlijke kwantumvoordeel zou alleen mogelijk zijn bij veel grotere dimensies dan die nodig zijn voor cryptografie, of vereist significante doorbraken in zowel theoretische protocollen als hardwareontwikkeling.

Kortom, deze studie biedt een realistische, hardware-gebaseerde weerlegging van de angst dat Grover's zoekalgoritme lattice-cryptografie snel zal breken, en bevestigt de robuustheid van de huidige NIST-standaarden tegen kwantaanvallen.