Simon's Algorithm for the Even-Mansour Cipher on Quantum Hardware

Dit artikel presenteert een proof-of-concept kwantumanalyse van de Even-Mansour-cijfer met behulp van het algoritme van Simon op NISQ-hardware, waarbij met succes geheime sleutels zijn hersteld voor constructies van 3 en 4 bits op de ibm_miami-processor, terwijl tegelijkertijd geheugenknelpunten in huidige circuitoptimalisatietools voor grotere sleutellengtes worden belicht.

De kern

Stel je voor dat je probeert een kluis te kraken die een zeer specifieke, lastige vergrendeling gebruikt. Dit artikel gaat over een team van onderzoekers dat probeerde die vergrendeling te openen met een nieuw soort "superhulpmiddel" dat een quantumcomputer wordt genoemd. Ze raden de combinatie niet zomaar; ze gebruikten een slimme wiskundige truc om het patroon te vinden dat verborgen zit in de vergrendeling.

Hier is de uitleg van hun experiment in eenvoudige bewoordingen:

De Vergrendeling: De Even-Mansour-cijfer

Stel je de Even-Mansour-cijfer voor als een eenvoudige maar stevige kluis. Het werkt als volgt:

1. Je plaatst een bericht (de zuivere tekst) in de kluis.
2. Je mengt het met een geheime sleutel (Sleutel 1).
3. Je voert het door een publieke, chaotische machine (een permutatie) die het in de war brengt.
4. Je mengt het opnieuw met een tweede geheime sleutel (Sleutel 2).
5. Het resultaat is het vergrendelde bericht.

Het doel van de aanvallers (de onderzoekers) was om uit te vinden wat die twee geheime sleutels waren.

Het Superhulpmiddel: Simons Algorithm

Normaal gesproken zou je, als je een geheime sleutel wilde vinden, misschien biljoenen combinaties één voor één moeten proberen. Dat is als proberen elke enkele sleutel op een gigantische sleutelbos te passen totdat er één past.

Maar de onderzoekers gebruikten Simons Algorithm. Stel je dit algoritme voor als een magische detective die niet direct naar de sleutel zoekt. In plaats daarvan zoekt het naar een verborgen ritme of een patroon.

• De onderzoekers stelden een speciale situatie op waarbij de vergrendeling zich op een rare manier gedroeg: als je de draaischijf een bepaalde hoeveelheid draaide (de geheime sleutel), eindigde de vergrendeling in exact dezelfde positie als wanneer je hem helemaal niet had gedraaid.
• Simons Algorithm is uitstekend in het vinden van deze "verborgen ritmes" (perioden) veel sneller dan een normale computer zou kunnen. Het is als luisteren naar een liedje en direct het ritme te weten, terwijl een normale computer elke afzonderlijke drumslag moet tellen.

Het Experiment: De Vergrendeling Bouwen op een Quantumcomputer

De onderzoekers wilden zien of deze magische detective daadwerkelijk zou werken op echte, fysieke hardware. Ze bouwden een kleine versie van de vergrendeling op een quantumcomputer genaamd IBM Miami.

1. Het Ontwerp (S-blokken): Om de vergrendeling te laten werken, hadden ze een "verwarmer" nodig (een S-blok). Ze bouwden deze verwarren met logica die lijkt op die welke wordt gebruikt in de beroemde AES-encryptiestandaard, maar dan veel kleiner (voor 3-bits en 4-bits sleutels).
2. Het Vertaalprobleem: Quantumcomputers spreken een andere taal dan gewone computers. De onderzoekers moesten hun klassieke "verwarmer"-ontwerpen vertalen naar een taal die de quantumcomputer kon begrijpen. Ze gebruikten een hulpmiddel genaamd DORCIS om deze vertaling te doen.
   • De Knelpunt: Dit hulpmiddel werkte uitstekend voor de kleine 3-bits en 4-bits vergrendelingen. Echter, toen ze probeerden een iets grotere 5-bits vergrendeling te vertalen, raakte het hulpmiddel zonder geheugen. Het was als proberen een enorme kaart in een klein zakje te vouwen; het papier paste gewoon niet. Dit stopte hen ervan om grotere sleutels te testen.
3. Het Ruis: Quantumcomputers zijn momenteel zeer gevoelig, als een huis van kaarten in een windstoot. Om het experiment stabiel te houden, gebruikten de onderzoekers speciale technieken (zoals "Dynamische Koppeling") om de qubits tot rust te brengen, vergelijkbaar met hoe je een camera vast zou houden om een duidelijke foto te maken in de wind.

De Resultaten

Ze voerden het experiment uit op twee kleine vergrendelingen: één met een 3-bits sleutel en één met een 4-bits sleutel.

• Succes: In beide gevallen vond de quantumcomputer succesvol het verborgen ritme. Uit dat ritme berekenden de onderzoekers de geheime sleutels.
• Herhaalbaarheid: Ze voerden de test vijf keer uit voor elke vergrendelingsgrootte, en het werkte elke keer.
• De Beperking: Zoals vermeld, konden ze geen 5-bits vergrendeling testen omdat het vertaalhulpmiddel (DORCIS) crashte door geheugenbeperkingen.

De Conclusie

Het artikel concludeert twee hoofdzaakken:

1. Het Werkt (voor nu): Simons Algorithm is een echte, werkende methode om dit specifieke type encryptie te kraken op huidige quantumhardware, maar alleen voor zeer kleine sleutels. Het bewijst dat quantumcomputers deze verborgen patronen theoretisch exponentieel sneller kunnen vinden dan klassieke computers.
2. De Hulpmiddelen Moeten Worden Geüpgraded: Hoewel de quantumcomputer zijn werk deed, botste de software die werd gebruikt om de "ontwerpen" voor de quantumcomputer voor te bereiden tegen een muur. Om in de toekomst grotere, realistischere vergrendelingen te kraken, hebben we betere hulpmiddelen nodig om deze ontwerpen te vertalen naar quantumcircuits zonder dat het geheugen opraakt.

Kortom: Ze bewezen dat het concept werkt op kleine schaal, maar het "bouwteam" (de softwarehulpmiddelen) moet sterker worden voordat ze de grote wolkenkrabbers kunnen bouwen.

Technische samenvatting

1. Probleemstelling

Het artikel behandelt de praktische haalbaarheid van het uitvoeren van kwantumaanvallen op cryptanalyse op symmetrische cijfers met behulp van huidige Noisy Intermediate-Scale Quantum (NISQ)-hardware. Specifiek richt het zich op de Even-Mansour (EM) cipher, een minimale blokchiffreconstructie gebaseerd op een publieke permutatie en twee geheime sleutels.

Hoewel het theoretische kader voor het kraken van de EM-cijfer met behulp van Simon's Algorithm goed gevestigd is (met een exponentiële snelheidswinst ten opzichte van klassieke aanvallen door het vinden van een verborgen periode), is de praktische implementatie beperkt gebleven. De kernuitdagingen zijn:

• Hardware-beperkingen: NISQ-apparaten lijden onder ruis, decoherentie en beperkte qubit-connectiviteit, waardoor diepe circuits (vereist voor complexe permutaties) moeilijk uit te voeren zijn.
• Knelpunten in circuitsynthese: Het converteren van klassieke cryptografische permutaties (S-blokken) naar geoptimaliseerde, reversibele kwantumcircuits is computatievraagsintensief. Bestaande tools falen vaak bij het schalen naar grotere sleutellengten vanwege geheugenbeperkingen.
• Implementatie van de Oracle: De aanval vereist het implementeren van de encryptiefunctie als een kwantum-oracle, wat het synthetiseren van niet-lineaire permutaties in kwantum-poorten inhoudt.

2. Methodologie

De auteurs hebben een proof-of-concept-aanval geïmplementeerd op de IBM ibm_miami processor. De methodologie omvatte drie hoofdfasen:

A. Cryptografische Constructie

• Cipher: Het Even-Mansour-schema $EM_{k_1, k_2}(x) = P(x \oplus k_1) \oplus k_2$, waarbij $P$ een publieke permutatie is en $k_1, k_2$ geheime sleutels.
• Permutatie ($P$): Voor $N=3$ en $N=4$ construeerden de auteurs bijectieve afbeeldingen geïnspireerd op de AES S-box. Deze werden gedefinieerd als inversie in het eindige veld $F_{2^N}$ gevolgd door een affiene transformatie.
• Aanvalsvector: De aanval definieert een functie $f(x) = EM(x) \oplus P(x)$. Deze functie heeft een verborgen periode $k_1$. Simon's algoritme wordt gebruikt om $k_1$ te vinden, waarna $k_2$ klassiek of via een eenvoudige kwantumquery wordt hersteld.

B. Kwantumcircuitsynthese (DORCIS)

• Toolchain: De auteurs gebruikten de DORCIS (Depth Optimized Quantum Implementation of Substitution Boxes) tool om de klassieke permutatietabellen te synthetiseren naar reversibele kwantumcircuits.
• Optimalisatie: DORCIS decomposeert permutaties in elementaire poorten (Pauli-X, Toffoli/CCNOT, SWAP) en minimaliseert de circuitdiepte.
• Schalingslimiet: De tool slaagde erin circuits te genereren voor $N=3$ en $N=4$, maar faalde voor $N=5$ vanwege een geheugenknelpunt op een high-performance CPU (3,9 TiB RAM), wat het genereren van circuits voor grotere instanties verhinderde.

C. Hardware-uitvoering en Foutmitigatie

Om de aanval uit te voeren op de ruizige ibm_miami processor, paste het team specifieke mitigeringsstrategieën toe:

• Qubit-mapping: Ze mapten logische qubits handmatig naar specifieke fysieke qubit-subgrafieken ($[0, 1, 2, 12, 11, 10]$ voor $N=3$ en $[0, 1, 2, 3, 13, 12, 11, 10]$ voor $N=4$) om de roostertopologie te benutten en de overhead van automatisch routing te vermijden.
• Dynamische Koppeling (DD): Er werden symmetrische sequenties van unitaires (bijv. afwisselende X-pulsen) toegepast op inactieve qubits om lage-frequentie omgevingsruis en kruisspraak te onderdrukken.
• Pauli Twirling: Logisch equivalente Pauli-operatorparen werden willekeurig ingevoegd voor en na poorten om coherente fouten om te zetten in stochastische Pauli-fouten, waardoor systematische fasevervormingen werden voorkomen die de structurele botsingen van het algoritme zouden kunnen verstoren.

3. Belangrijkste Bijdragen

1. Eerste Praktische Demonstratie: Dit is een succesvolle proof-of-concept die geheime sleutelherstel voor de Even-Mansour cipher demonstreert op daadwerkelijke kwantumhardware ($N=3$ en $N=4$).
2. Validatie van Foutmitigatie: Het artikel valideert dat het combineren van Dynamische Koppeling en Pauli Twirling het mogelijk maakt dat Simon's algoritme effectief functioneert ondanks de diepe circuitdieptes en ruis inherent aan NISQ-apparaten.
3. Identificatie van Klassieke Knelpunten: De studie benadrukt dat de beperkende factor voor het schalen van deze aanvallen momenteel de klassieke voorverwerking (circuitsynthese) is en niet de kwantumhardware zelf. De DORCIS-tool faalde bij $N=5$ vanwege geheugenbeperkingen.
4. Empirische Data: De auteurs bieden gedetailleerde statistische verdelingen van meetresultaten, die aantonen dat de experimentele resultaten overeenkomen met theoretische voorspellingen wanneer ruis wordt meegerekend.

4. Resultaten

• 3-bit Geval ($N=3$):
  • Succesvol herstel van de geheime sleutel $k_1 = (0, 1, 0)$ en $k_2 = (1, 1, 0)$.
  • De circuitdiepte was 23 (T-depth 3).
  • Na 5 onafhankelijke experimenten (105 shots elk) piekte de meetverdeling duidelijk bij de vectoren die orthogonaal zijn aan de ware periode, waardoor een succesvolle lineaire algebra-herstel van de sleutel mogelijk was.
• 4-bit Geval ($N=4$):
  • Succesvol herstel van $k_1 = (0, 1, 0, 1)$ en $k_2 = (1, 1, 0, 1)$.
  • De circuitdiepte steeg naar 54 (T-depth 7).
  • Ondanks de toegenomen diepte en ruis bleef de verdeling van resultaten duidelijk genoeg om het stelsel lineaire vergelijkingen voor de sleutel op te lossen.
• Foutanalyse:
  • De auteurs modelleerden de ruis als een depolariserend kanaal. Ze schatten een ruisparameter $p \approx 0,434$ op basis van poortfoutpercentages en het totale aantal pulsen.
  • De experimentele data kwam overeen met de theoretische ruizige verdeling, wat bevestigt dat de afwijkingen te wijten waren aan hardware-ruis en niet aan een falen van het algoritme.
• Schalingsfalen: De DORCIS-tool kon geen circuit genereren voor $N=5$, wat aangeeft dat huidige klassieke synthesetools nog niet schaalbaar zijn voor grotere sleutellengten.

5. Betekenis

• Theoretische Validatie: De resultaten bevestigen dat de theoretische exponentiële snelheidswinst van Simon's algoritme in de praktijk haalbaar is voor symmetrische cijfers, mits de sleutellengte klein genoeg is voor huidige hardware.
• Veiligheidsimplicaties: Het onderstreept de kwetsbaarheid van symmetrische constructies zoals Even-Mansour (en bij uitbreiding, 1-rond AES) voor kwantaanvallen als een encryptie-oracle toegankelijk is in superpositie.
• Hardware versus Software Knelpunt: Het artikel verschuift de focus van de uitdaging van "kunnen we het kwantumalgoritme draaien?" naar "kunnen we het circuit synthetiseren?". Het suggereert dat toekomstige vooruitgang in kwantumcryptanalyse sterk afhankelijk is van de ontwikkeling van meer schaalbare klassieke synthesetools (mogelijk met behulp van machine learning of heuristieken) en niet alleen van het wachten op betere qubits.
• NISQ Leefbaarheid: Het demonstreert dat met geavanceerde foutmitigatie en handmatige qubit-mapping complexe cryptanalytische algoritmes correcte resultaten kunnen opleveren op huidige, ruizige hardware.