Quantum Circuit Realization and Grover Cryptanalysis of the Hybrid ARX-SPN Cipher GFSPX

Dit artikel presenteert een op qubits geoptimaliseerde implementatie van een quantumcircuit voor de lichte hybride ARX-SPN-cijfer GFSPX en evalueert de post-kwantumveiligheid ervan via een geparalleliseerde Grover-aanval, waarbij een totale quantumkost van $1.12 \times 2^{159}$ poorten wordt blootgelegd die, hoewel onder de NIST-niveau-1-drempels, een superieure weerstand toont in vergelijking met andere lichte ontwerpen.

De kern

Stel je voor dat je een zeer speciale, lichtgewicht digitale vergrendeling (genaamd GFSPX) hebt, ontworpen om data te beschermen op kleine apparaten zoals slimme sensoren of RFID-tags. Deze vergrendeling is gebouwd om snel te zijn en zeer weinig energie te verbruiken, waardoor hij perfect is voor het "Internet of Things".

Echter, er komt een nieuw soort "superhulpmiddel" op: een Quantumcomputer. In tegenstelling tot gewone computers die sleutels één voor één controleren, kan een quantumcomputer veel sleutels tegelijk controleren, waardoor deze vergrendelingen mogelijk veel sneller gekraakt kunnen worden. Dit artikel stelt een simpele vraag: Als een quantumcomputer probeert deze specifieke vergrendeling te breken, hoe moeilijk zal dat dan eigenlijk zijn?

Hier is de uiteenzetting van hun bevindingen met behulp van alledaagse analogieën:

1. Het Ontwerp van de Vergrendeling: Een Hybride Motor

De GFSPX-vergrendeling is niet gebouwd met slechts één type mechanisme. Het is een hybride, zoals een auto die zowel een benzine- als een elektromotor gebruikt.

• Het "Benzine"-deel (ARX): Dit gebruikt eenvoudige wiskundige bewerkingen (Optellen, Roteren, XOR) die zeer efficiënt zijn, maar veranderingen door de data wat langzamer kunnen verspreiden.
• Het "Elektrische"-deel (SPN): Dit gebruikt een complex substitutienetwerk (zoals het schudden van een kaartspel) dat veranderingen zeer snel verspreidt.
• Het Resultaat: Door ze te combineren, is de vergrendeling snel en efficiënt. De auteurs hebben een digitaal blauwdruk van deze vergrendeling gemaakt, specifiek voor een quantumcomputer, om precies te zien hoe deze van binnen werkt.

2. Het Quantum-Blauwdruk: De Schakeling Bouwen

Om de vergrendeling te testen, moesten de onderzoekers een "quantumschakeling" bouwen. Denk hierbij aan het bouwen van een miniatuur, reversibele fabriek waar elke stap perfect ongedaan gemaakt kan worden (zodat er geen informatie verloren gaat).

• De Uitdaging: Quantumcomputers zijn fragiel. Je kunt data niet zomaar kopiëren; je moet zeer zorgvuldig omgaan met de "qubits" (de quantumbits, zoals kleine draaiende tolletjes).
• De Oplossing: De onderzoekers optimaliseerden het ontwerp om het minimale aantal qubits te gebruiken (209 stuks). Ze gebruikten een slimme truc genaamd een "ripple-carry adder" voor de wiskundige delen, wat vergelijkbaar is met een zeer efficiënte assemblagelijn die geen ruimte verspilt.
• De Voetafdruk: Het uiteindelijke blauwdruk is compact en vereist een "fabrieksvloer" van 209 qubits en een specifiek aantal stappen (poorten) om één volledige encryptie uit te voeren.

3. De Aanval: De "Grover"-Zoektocht

Om de vergrendeling te breken, gebruikt een quantumcomputer het Grover-algoritme.

• De Analogie: Stel je een gigantische bibliotheek voor met $2^{128}$ boeken (een getal zo groot dat het moeilijk te bevatten is), en slechts één boek bevat de juiste sleutel.
  • Een gewone computer is als een bibliothecaris die één boek per keer controleert. Het zou eeuwig duren.
  • Een quantumcomputer is als een magische bibliothecaris die veel boeken tegelijk kan controleren. Hij vindt het juiste boek in ongeveer de wortel van de tijd.
• De Valstrik: Om ervoor te zorgen dat de quantumcomputer niet het verkeerde boek kiest (een "vals positief"), lieten de onderzoekers de computer drie verschillende vergrendelingen controleren (met drie verschillende paren vergrendelde/ontgrendelde berichten) tegelijkertijd. Als een sleutel alle drie opent, is het zeker de juiste.

4. Het Oordeel: Sterk, Maar Geen "Post-Quantum"-Bewijs

De onderzoekers berekenden de totale "kosten" van deze quantum-aanval.

• De Kosten: Ze ontdekten dat het breken van de vergrendeling een enorme hoeveelheid rekenkracht vereist, ongeveer gelijk aan $1,12 \times 2^{159}$ bewerkingen.
• De Standaard: Het Amerikaanse National Institute of Standards and Technology (NIST) heeft een "veiligheidsbalk" voor de toekomst vastgesteld. Om als echt veilig tegen quantumcomputers te worden beschouwd (Veiligheidsniveau 1), moet een vergrendeling kosten hebben van ten minste $2^{170}$.
• Het Resultaat: De GFSPX-vergrendeling ligt onder de veiligheidsbalk. Hij is niet veilig genoeg voor de strengste post-quantum standaarden.
  • Echter, het artikel merkt op dat GFSPX, vergeleken met andere lichtgewicht vergrendelingen, eigenlijk een van de moeilijkst te breken is. Hij zit in een "sweet spot" waar hij zeer efficiënt is voor kleine apparaten, maar toch een behoorlijke weerstand biedt tegen quantum-aanvallen, zelfs als hij niet de hoogste veiligheidstest haalt.

5. De Conclusie

Het artikel concludeert dat hoewel deze hybride vergrendeling uitstekend is voor huidige, hulpbronnen-beperkte apparaten, de sleutellengte van 128 bits simpelweg te klein is om een vastberaden quantum-aanval in de toekomst te overleven.

• De Ruil: Je kunt kiezen voor een vergrendeling die klein en snel is (goed voor de sensoren van vandaag), of een vergrendeling die groot en traag is (goed voor toekomstige quantumveiligheid), maar dit specifieke ontwerp probeert beide te doen en valt iets te kort op het gebied van "toekomstige veiligheid".
• Toekomstig Advies: Om dit ontwerp echt quantum-proof te maken, suggereren de auteurs om de sleutel langer te maken (zoals 192 of 256 bits) of de wiskundige delen aan te passen om ze nog moeilijker te maken voor quantumcomputers om te verwerken.

Kortom: GFSPX is een zeer slimme, efficiënte vergrendeling die moeilijker te kraken is dan de meeste van zijn collega's, maar hij is niet helemaal sterk genoeg om het hoofd te bieden aan de superkrachtige quantumcomputers van de toekomst zonder enkele upgrades.

Technische samenvatting

Technische Samenvatting: Quantum Circuit Realisatie en Grover Cryptanalyse van de Hybride ARX-SPN Cipher GFSPX

Probleemstelling
De opkomst van quantumcomputing vormt een fundamentele uitdaging voor de beveiliging van klassieke symmetrische primitieven. Waar Shor's algoritme de publieke-sleutelcryptografie bedreigt, biedt Grover's algoritme een kwadratische versnelling voor ongestructureerd zoeken, wat effectief de veiligheidsmarge van symmetrische constructies halveert. Bijgevolg vereisen lightweight blockciphers (BC's), ontworpen voor resource-beperkte omgevingen zoals het Internet of Things (IoT) en RFID, een rigoureuze herbeoordeling van hun post-quantum weerbaarheid. Specifiek is er behoefte om de quantumresources te kwantificeren die nodig zijn om een aanval op de sleutelherwinning uit te voeren op hybride ontwerpen die Addition-Rotation-XOR (ARX) en Substitution-Permutation Network (SPN) paradigma's combineren.

Methodologie
De auteurs presenteren een uitgebreide quantumcircuitrealisatie en Grover-cryptanalyse van GFSPX, een lightweight blockcipher met een 64-bits datablok en een 128-bits geheime sleutel. GFSPX maakt gebruik van een 4-branch Generalized Feistel Structure (GFS) die twee distincte functionele blokken integreert: een op ARX gebaseerde functie ($F_1$) voor non-lineariteit en een 32-bits SPN-structuur ($F_2$) voor snelle diffusie.

De methodologie verloopt in drie fasen:

1. Quantum Circuit Realisatie: De klassieke structuur van GFSPX wordt gemapt naar een reversibel quantumcircuit. De auteurs benutten de inherente reversibiliteit van het Feistel-netwerk om het gebruik van ancilla-qubits te minimaliseren.
   • $F_1$ (ARX): Geïmplementeerd met behulp van een compacte ripple-carry adder (RCA) gebaseerd op de architectuur van Cuccaro et al. Deze aanpak minimaliseert de qubit-overhead door het laatste carry-bit voor modulaire optelling over te slaan en gebruik te maken van in-place majority (MAJ) en UnMajority-and-Add (UMA) poorten.
   • $F_2$ (SPN): De S-boxlaag (gebaseerd op PRESENT) wordt gesynthetiseerd met een minimaal aantal CNOT- en Toffoli-poorten zonder extra ancilla's. De permutatielaag (P-laag) wordt geïmplementeerd via paralleliseerbare SWAP-poorten om een lage circuitdiepte te behouden.
   • Sleutelplanning: De 128-bits mastersleutelplanning wordt gerealiseerd als een unitaire evolutie die een 113-bits linkse cyclische rotatie, S-box-substituties en XOR's met de rondeteller omvat, geoptimaliseerd voor in-place uitvoering.
2. Resource Schatting: De quantumkost wordt berekend met behulp van standaard decompositiemetrics (NOT- en CNOT-kost = 1, Toffoli-kost = 6). De analyse evalueert zowel een basiskost (exclusief SWAP-routing-overhead) als een bovengrens (decompositie van SWAP's in drie CNOT's).
3. Grover Cryptanalyse: Een geparelleerde Grover-orakel ($U_f$) wordt geconstrueerd om de cipher te evalueren tegen aanvallen op sleutelherwinning. Om spurious matches in de 128-bits sleutelruimte te elimineren, maakt het orakel gebruik van drie plaintext-ciphertextparen ($r=3$). De aanvalcomplexiteit wordt geschat door de resource-metrics van het orakel te schalen met het optimale aantal Grover-iteraties ($\approx \frac{\pi}{4}2^{64}$).

Belangrijkste Bijdragen

• Geoptimaliseerde Quantum Implementatie: Het paper biedt een qubit-geoptimaliseerd quantumcircuit voor GFSPX, met een footprint van 209 qubits. Het ontwerp bereikt een basale quantumkost van 32.498 poorten met een circuitdiepte van 7.617.
• Analyse van Hybride Architectuur: De studie detailleert de resourceverdeling van een hybride ARX-SPN-ontwerp, en toont aan dat hoewel de modulaire optellingsprimitief de totale poorttelling domineert, de geparelleerde permutatielagen in het SPN-component helpen een concurrerende poort-tot-diepteverhouding te behouden.
• Kwantitatieve Beveiligingsbeoordeling: De auteurs construeren een Grover-orakel met behulp van drie plaintext-ciphertextparen en berekenen de totale aanvalskost onder het MAXDEPTH-kader van NIST. De analyse onthult een totale quantum-aanvalskost van ongeveer $1,12 \times 2^{159}$ poorten voor $r=3$.
• Comparatieve Benchmarking: De implementatie wordt gebenchmarkd tegen andere lightweight ciphers (zoals PRESENT, GIFT, SIMON, SPECK). GFSPX bereikt de laagste kost-tot-diepteverhouding (4,27) onder de vergeleken ontwerpen, wat wijst op een hoge parallelle uitvoeringsefficiëntie.

Resultaten

• Resource Metrics: Het volledige 20-rond GFSPX-circuit vereist 209 qubits. De basale kost is 32.498, stijgend tot 47.789 wanneer SWAP-routing-overhead wordt meegerekend. De circuitdiepte is 7.617.
• Aanvalcomplexiteit: De totale quantumkost voor een aanval op sleutelherwinning wordt geschat op $1,12 \times 2^{159}$ (voor $r=3$).
• Beveiligingsclassificatie: Onder het NIST Post-Quantum Cryptography-kader vereist de beveiligingsdrempel van Niveau 1 (equivalent aan AES-128) een totale aanvalskost van ten minste $2^{170}$. De geschatte kost voor GFSPX ($2^{159}$) ligt onder deze drempel.
• Ontwerpafwegingen: Hoewel GFSPX een hogere weerstand tegen quantum-aanvallen toont dan veel pure SPN-ontwerpen (die zich rond $2^{152}$ clusteren), voldoet het niet aan de strikte beveiligingscriteria van Niveau 1 voor een sleutellengte van 128 bits. De kost van het hybride ontwerp wordt sterk beïnvloed door het ARX-component (modulaire optelling), waardoor het beveiligingsprofiel dichter bij ARX-gebaseerde ciphers zoals SIMON en SPECK ligt.

Betekenis
Het paper stelt dat de bevindingen kritieke inzichten bieden in de balans tussen klassieke hardware-efficiëntie en quantum-weerbaarheid voor cryptografische ontwerpen van de volgende generatie. De studie benadrukt een fundamentele afweging: hoewel hybride ARX-SPN-constructies robuuste klassieke prestaties bieden en een betere quantumweerstand dan pure SPN-ontwerpen, blijft een sleutellengte van 128 bits structureel onvoldoende om NIST Niveau 1-beveiliging te bereiken tegen geavanceerde quantumadversarissen. De auteurs suggereren dat toekomstig onderzoek zich moet richten op het verlengen van sleutellengtes (bijvoorbeeld naar 192 of 256 bits) of het optimaliseren van reversibele modulaire-optelprimitieven om veiligheidsmarges te verbeteren. De in dit werk vastgestelde methodologie dient als een rigoureus kader voor het evalueren van andere hybride ontwerpen in resource-beperkte omgevingen.