A compact QUBO encoding of computational logic formulae demonstrated on cryptography constructions

Dit paper presenteert een compacte QUBO-encodering voor cryptografische algoritmen die, door het oplossen van speciale boolese logische formules, de variabelehoeveelheid aanzienlijk reduceert ten opzichte van eerdere resultaten en zo de kwetsbaarheid voor toekomstige quantum-annealers vergroot.

De kern

De Kern: Het Oplossen van Cryptografische Puzzels met Minder Hulpstukken

Stel je voor dat je een enorme, ingewikkelde puzzel moet oplossen. Deze puzzel is een cryptografisch algoritme (zoals AES of SHA), een digitaal slot dat gebruikt wordt om berichten veilig te houden. Om dit slot te kraken (of te testen of het veilig is), moet je de "sleutel" vinden.

In de wereld van de kwantumcomputers (specifiek machines die "kwantum-annealing" gebruiken) wordt dit soort puzzels vertaald naar een wiskundig probleem genaamd QUBO. Je kunt QUBO zien als een enorme, digitale doolhof. Hoe groter en complexer de doolhof, hoe moeilijker het is om de uitgang te vinden.

Het probleem: Tot nu toe waren deze digitale doolhoven voor cryptografie enorm groot. Ze hadden duizenden "ruimtes" (variabelen) nodig. De huidige kwantumcomputers zijn echter nog niet groot genoeg om zo'n gigantisch doolhof in één keer te bevatten. Het is alsof je probeert een olifant in een kleine auto te proppen.

De oplossing van dit artikel: De onderzoekers hebben een nieuwe manier bedacht om deze doolhoven veel compacter te maken. Ze hebben de "ruimtes" in de doolhof drastisch verkleind, zonder de logica te veranderen. Hierdoor passen de puzzels nu veel makkelijker in de huidige (en toekomstige) kwantumcomputers.

---

Hoe hebben ze dit gedaan? (De Analogieën)

Om dit te begrijpen, kijken we naar drie belangrijke concepten uit het artikel:

1. De "Vervangende Hulpstukken" (Substitution Variables)

Stel je voor dat je een recept hebt met een stap: "Meng 500 gram bloem, 2 eieren en 300 gram suiker."
In de oude manier van coderen (de oude QUBO), zou je voor elke gram bloem, elk ei en elke gram suiker een aparte variabele moeten hebben. Dat zijn duizenden variabelen!

De onderzoekers zeggen: "Wacht even. Laten we dat mengsel gewoon 'Deeg' noemen."
Ze introduceren een vervanging: in plaats van alle losse ingrediënten te tellen, maken ze één nieuwe variabele die staat voor het hele mengsel.

• Oude manier: 10.000 losse blokjes.
• Nieuwe manier: 1 blokje "Deeg" + een paar regels die uitleggen hoe je het deeg maakt.

Dit is wat ze substitutie-variabelen noemen. Ze hebben slimme manieren gevonden om grote groepen logische stappen samen te vatten in één klein blokje, waardoor de totale grootte van de puzzel explodeert (in positieve zin: hij wordt kleiner!).

2. Het "Squeezen" van de Wiskunde (Root Squeezing)

Stel je voor dat je een lange rubberen slang hebt die een bepaald bereik moet afdekken (bijvoorbeeld getallen van 1 tot 100).

• Oude methode: Je hebt een variabele nodig voor elke stap in de slang.
• Nieuwe methode (Root Squeezing): De onderzoekers hebben een wiskundige truc bedacht (het Root Squeezing Theorem). Ze laten de slang "knijpen" op twee punten tegelijk. Hierdoor kunnen ze dezelfde lengte afdekken met één variabele minder.

Het klinkt als een klein verschil, maar in de wereld van duizenden variabelen is het verschil tussen "past net niet" en "past perfect" enorm. Door deze knijp-truc toe te passen op logische operaties (zoals OF, EN en XOR), hebben ze duizenden variabelen kunnen besparen.

3. De Cryptografie Test (AES, MD5, SHA)

De onderzoekers hebben hun nieuwe methode getest op de beroemdste digitale sloten ter wereld:

• AES: Het slot dat gebruikt wordt voor beveiligde communicatie (zoals bankzaken en WhatsApp).
• SHA/MD5: De "vingerafdrukken" van bestanden (hashes).

Het resultaat:
Voor AES-256 (een van de veiligste sloten) hadden eerdere methoden een QUBO-puzzel nodig met bijna 250.000 variabelen.
Met hun nieuwe methode hebben ze dit teruggebracht tot ongeveer 30.000 variabelen.

• Analogie: Het is alsof je eerder een vrachtwagen nodig had om je spullen te vervoeren, maar nu past alles in een kleine bestelbus.

Waarom is dit belangrijk?

1. Kwantumcomputers worden sterker: Er komen binnenkort kwantumcomputers die ongeveer 30.000 variabelen kunnen verwerken. Met de oude methoden waren cryptografische puzzels te groot voor deze machines. Met deze nieuwe methode zijn ze plotseling haalbaar.
2. Beveiliging testen: Dit betekent dat we cryptografische systemen sneller en beter kunnen testen op zwakke plekken. Als een slot te makkelijk te kraken is met een kwantumcomputer, moeten we het vervangen door een sterker slot.
3. Efficiëntie: De nieuwe codes zijn niet alleen kleiner, maar ook "spijker" (ze hebben minder verbindingen nodig), wat ze makkelijker maakt om op de hardware te plaatsen.

Conclusie in één zin

De onderzoekers hebben een slimme manier bedacht om enorme, ingewikkelde cryptografische puzzels in te krimpen tot een formaat dat past in de huidige en toekomstige kwantumcomputers, door slimme "samenvattingen" en wiskundige trucs toe te passen die duizenden variabelen besparen.

Kortom: Ze hebben de digitale sleutelgat-puzzel zo klein gemaakt dat hij nu in de sleutelgat van de kwantumcomputer past, wat betekent dat we in de toekomst veel sneller kunnen zien of onze digitale sloten echt veilig zijn.

Technische samenvatting

Probleemstelling

Het artikel adresseert de uitdaging om logische formules en cryptografische algoritmen efficiënt te vertalen naar het Quadratic Unconstrained Binary Optimization (QUBO) formaat. QUBO is cruciaal voor het oplossen van NP-moeilijke problemen op kwantum-ontvlechtingen (quantum annealers) en andere speciale hardware.

De huidige staat van de techniek heeft echter twee grote beperkingen:

1. Variabele-explosie: Bestaande methoden (vaak gebaseerd op Tseitin-transformaties naar CNF) leiden tot QUBO-instanties met een zeer groot aantal logische variabelen. Dit overschrijdt vaak de capaciteit van huidige kwantumhardware (die rond de 30.000 logische variabelen kan verwerken).
2. Coëfficiëntgrootte: Veel encoding-methodes genereren QUBO-matrices met zeer grote coëfficiënten, wat problematisch is voor hardware met beperkte numerieke precisie.

Het doel is om een compactere encoding te vinden die het aantal variabelen minimaliseert, de matrix sparsiteit behoudt en de grootte van de coëfficiënten beperkt, specifiek voor complexe cryptografische functies zoals AES, MD5 en SHA.

Methodologie

De auteurs ontwikkelen een nieuwe strategie die gebaseerd is op het oplossen van Integer Linear Programming (ILP) problemen om optimale encoding-patronen te vinden.

1. ILP-gedreven Patroonherkenning:

   • In plaats van directe transformatie, formuleren ze het zoeken naar een compacte QUBO-encoding als een ILP-probleem.
   • Ze definiëren een kwadratische functie $g(x, s)$ (waarbij $x$ de invoer is en $s$ substitutievariabelen) die 0 moet zijn voor geldige min-termen (min-terms) en strikt positief voor alle andere combinaties.
   • Door dit ILP-probleem op te lossen voor kleine, beheersbare SAT-instanties, ontdekken ze generieke patronen die schaalbaar zijn naar grotere problemen.

2. Theoretische Innovaties:

   • Root Squeezing Theorem: Een nieuw theorema dat toelaat om bereikbeperkingen (range constraints) te coderen met minder substitutievariabelen. In plaats van een kwadraat $(\sum x_i - T)^2$ te gebruiken, gebruiken ze een product van twee termen: $(\sum x_i - f_1(s)) \cdot (\sum x_i - f_2(s))$. Omdat $f_1$ en $f_2$ slechts 1 van elkaar verschillen, kan één binaire representatie van $s$ twee waarden dekken, wat één variabele bespaart.
   • Pariteit (XOR) Encoding: Voor XOR-clausules wordt een methode ontwikkeld die het aantal benodigde substitutievariabelen minimaliseert door gebruik te maken van de eigenschappen van sommen van binaire variabelen.
   • Substitutievariabelen: Ze onderscheiden tussen "pre-constrained", "strong" en "weak" substitutievariabelen om hergebruik in complexe circuits mogelijk te maken.

3. Toepassing op Cryptografie:

   • De methode wordt toegepast op de bouwstenen van cryptografische algoritmen:
     • AES: De S-box (vervanging) wordt ontbonden in algebraïsche normal forms (ANF) over Galois-velden ($GF(2^8)$). De auteurs gebruiken een heuristiek om XOR-expressies te hergebruiken en minimaliseren het aantal AND-poorten.
     • Hash-functies (MD5, SHA-1, SHA-256): Ze coderen modulaire optellingen en logische functies (zoals ternaire selectie en meerderheidsfuncties) met de nieuwe patronen. Ze introduceren een "block-wise" strategie voor optellingen om de grootte van de coëfficiënten te beheersen.

Belangrijkste Bijdragen

• Generieke Encoding-strategie: Een methode om CNF, DNF, ANF en PES (Product of Exclusive Sums) formules efficiënt om te zetten naar QUBO met het minimale aantal substitutievariabelen.
• Root Squeezing Theorem: Een wiskundig bewezen methode om de hoeveelheid benodigde variabelen voor bereikbeperkingen te reduceren.
• Optimalisatie van Cryptografische Circuits: Het succesvol toepassen van deze theorie op de S-box van AES en de interne logica van hash-functies, wat leidt tot aanzienlijke reducties in variabele-aantallen.
• Openbare Beschikbaarheid: De gegenereerde QUBO-instanties zijn beschikbaar gesteld via een GitHub-repository.

Resultaten

De auteurs hebben hun methode getest op de volgende algoritmen en vergeleken met eerder gepubliceerde resultaten (voornamelijk uit referentie [36]):

• AES-256: De QUBO-encoding vereist slechts 31.242 variabelen voor decryptie. Dit is een reductie van >8x (of slechts 12% van de grootte) vergeleken met de beste eerdere resultaten (~250.000 variabelen).
• AES-128/192: Eveneens significante reducties (respectievelijk 24% en 12% van de vorige grootte).
• Hash-functies:
  • MD5: Reductie van ~17.280 naar 10.272 variabelen (bij gebruik van blokgrootte B=6).
  • SHA-256: Reductie van ~47.808 naar 30.255 variabelen.
• Sparsiteit en Coëfficiënten: De gegenereerde matrices zijn zeer spaarzaam (dichtheid tussen 0,04% en 0,52%). De auteurs tonen aan dat er een afweging is tussen het aantal variabelen en de grootte van de coëfficiënten: kleinere blokken (B=1) geven kleinere coëfficiënten maar meer variabelen, terwijl grotere blokken (B=6) minder variabelen geven maar grotere coëfficiënten.

Significantie en Toekomstperspectief

• Kwamteerbaarheid van Cryptografie: De drastische reductie in het aantal variabelen maakt het mogelijk om cryptografische problemen (zoals het breken van AES-256) te benaderen met toekomstige kwantum-ontvlechtingen die rond de 30.000 logische variabelen kunnen verwerken. Hoewel AES-256 nog steeds buiten bereik is voor huidige hardware, toont dit aan dat de drempel lager ligt dan eerder werd gedacht.
• Efficiëntie voor Hardware: De lage dichtheid van de matrices is ideaal voor hardware met beperkte connectiviteit (zoals D-Wave kwantum-ontvlechtingen), omdat minder "chaining" (koppelen van qubits) nodig is.
• Methodologische Vooruitgang: Het artikel biedt een blauwdruk voor het vertalen van complexe logische formules naar QUBO, wat nuttig is voor veel andere NP-moeilijke problemen buiten cryptografie (zoals planning en optimalisatie).
• Beperkingen: Het vinden van de absolute optimale boolean circuit-representatie (bijv. voor vermenigvuldiging in $GF(2^8)$) blijft een NP-hard probleem. De auteurs geven toe dat hun zoektocht naar de absolute minimum voor bepaalde sub-problemen (zoals de S-box) niet volledig geslaagd is, maar dat hun huidige resultaten al een enorme stap voorwaarts zijn.

Samenvattend presenteert dit werk een doorbraak in de compactheid van QUBO-encodings, waardoor cryptografische uitdagingen binnen het bereik van de volgende generatie kwantumcomputers komen.