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

Die vorgestellte Arbeit präsentiert eine kompakte QUBO-Kodierung für kryptografische Algorithmen wie AES und SHA, die durch die Lösung von Booleschen Logikformeln als ganzzahlige Optimierungsprobleme eine drastische Reduktion der Variablenanzahl im Vergleich zu bisherigen Ergebnissen ermöglicht und damit die Anfälligkeit dieser Verfahren für zukünftige Quanten-Annealer erhöht.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, ein riesiges, verschlüsseltes Schloss zu knacken. Um das Schloss zu öffnen, müssen Sie den richtigen Schlüssel finden. In der Welt der Computerwissenschaft ist das „Schloss" ein komplexes mathematisches Problem (wie ein Verschlüsselungs-Algorithmus), und der „Schlüssel" ist die Lösung, die ein Computer finden muss.

Dieser wissenschaftliche Artikel beschreibt eine neue, extrem effiziente Methode, um diese komplizierten mathematischen Schlösser in eine Sprache zu übersetzen, die eine spezielle Art von zukünftigen Computern – sogenannte Quanten-Annealer – verstehen und lösen können.

Hier ist die Erklärung in einfachen Worten, mit ein paar kreativen Vergleichen:

1. Das Problem: Der überfüllte LKW

Stellen Sie sich vor, Sie wollen einen riesigen Haufen von Gegenständen (die mathematischen Regeln der Verschlüsselung) in einen LKW (den Computer) laden, um sie zu einem Zielort zu bringen.

• Die alte Methode: Bisher mussten die Forscher jeden einzelnen Gegenstand einzeln verpacken und in den LKW stapeln. Das Ergebnis war ein riesiger Haufen, der viel zu groß für den LKW war. Der LKW (der aktuelle Quantencomputer) hatte nicht genug Platz, um alles zu transportieren.
• Das Ziel: Die Forscher wollten herausfinden, wie man diese Gegenstände so clever stapelt und verpackt, dass sie viel weniger Platz einnehmen, ohne dass etwas kaputtgeht.

2. Die Lösung: Der „QUBO"-Puzzle-Koffer

Die Sprache, die diese Quantencomputer verstehen, heißt QUBO. Man kann sich QUBO wie ein riesiges, quadratisches Puzzle vorstellen. Jedes Puzzleteil ist eine Variable (eine Ja/Nein-Entscheidung).

• Je mehr Puzzleteile Sie brauchen, desto schwieriger ist es, das Puzzle zu lösen.
• Die Forscher haben eine neue Art gefunden, die mathematischen Regeln (wie „UND", „ODER" und „XOR" in der Logik) in dieses Puzzle zu übersetzen.

Der Trick:
Statt für jede kleine Regel ein eigenes, großes Puzzleteil zu bauen, haben sie entdeckt, wie man mehrere Regeln zu einem einzigen, kompakten Baustein zusammenfügt.

• Analogie: Stellen Sie sich vor, Sie bauen eine Mauer. Die alte Methode war, jeden Stein einzeln zu setzen. Die neue Methode ist wie das Bauen von vorgefertigten Wandeinheiten. Sie brauchen viel weniger Steine (Variablen), um die gleiche Mauer zu bauen.

3. Die Entdeckung: Das „Wurzel-Quetsch-Theorem"

Im Herzen dieser neuen Methode steckt ein mathematisches Prinzip, das die Autoren das „Wurzel-Quetsch-Theorem" (Root Squeezing Theorem) nennen.

• Stellen Sie sich vor: Sie haben eine Waage. Auf der einen Seite liegt eine Zahl, auf der anderen Seite eine andere. Sie wollen, dass die Waage im Gleichgewicht ist (Null).
• Normalerweise brauchen Sie viele Gewichte (Variablen), um die Waage perfekt auszugleichen.
• Die Forscher haben entdeckt, wie man die Gewichte so anordnet, dass sie sich gegenseitig „quetschen" oder überlappen können, ohne dass die Waage kippt. Das spart enorm viel Platz. Sie brauchen fast die Hälfte (oder weniger) der Gewichte, die man früher für nötig hielt.

4. Der Test: Die großen Verschlüsselungen

Um zu beweisen, dass ihre Methode funktioniert, haben sie sie auf die berühmtesten und sichersten Verschlüsselungen der Welt angewendet:

• AES: Das Standard-Schloss für Bankdaten und sichere Nachrichten.
• MD5, SHA: Die digitalen Fingerabdrücke, die sicherstellen, dass eine Datei nicht manipuliert wurde.

Das Ergebnis:

• Bei AES-256 (einem sehr starken Schloss) haben sie die Anzahl der benötigten Puzzleteile um das 8-fache reduziert.
• Früher hätte man für AES-256 einen LKW gebraucht, der 250.000 Teile transportiert. Mit ihrer Methode passen nur noch etwa 30.000 Teile in den LKW.
• Das ist wie der Unterschied zwischen einem riesigen Container-Schiff und einem kleinen Sportboot.

5. Warum ist das wichtig? (Die Zukunft)

Warum sollten wir uns dafür interessieren?

• Quantencomputer kommen: Es gibt neue Computer (Quanten-Annealer), die in der Lage sind, diese QUBO-Puzzles extrem schnell zu lösen. Aber sie haben nur Platz für etwa 30.000 Puzzleteile.
• Die Gefahr: Mit der alten Methode waren die Verschlüsselungen zu groß für diese Computer. Mit der neuen Methode der Autoren passen die Verschlüsselungen plötzlich in den Computer.
• Das Fazit: Das bedeutet, dass diese Verschlüsselungen in Zukunft von diesen Quantencomputern „geknackt" werden könnten. Das ist ein Weckruf für die Sicherheitswelt: Wir müssen noch sicherere Schlösser bauen, bevor diese neuen Computer allgegenwärtig sind.

Zusammenfassung in einem Satz

Die Autoren haben einen genialen „Falt-Trick" entwickelt, um riesige mathematische Verschlüsselungsprobleme so klein zu falten, dass sie in die begrenzten Kapazitäten der nächsten Generation von Quantencomputern passen – was zeigt, wie schnell unsere digitale Sicherheit durch neue Technologien herausgefordert werden könnte.

Technische Zusammenfassung

Titel: Eine kompakte QUBO-Codierung von Berechnungslogikformeln, demonstriert an Kryptostrukturen

Autoren: Gregory Morse, Tamás Kozsik, Oskar Mencer, Péter Rakyta.

---

1. Problemstellung

Das Ziel der Arbeit ist die Weiterentwicklung des State-of-the-Art bei der Formulierung von Quadratic Unconstrained Binary Optimization (QUBO) Problemen, mit einem spezifischen Fokus auf Kryptoalgorithmen.

• Herausforderung: Die Umwandlung logischer Probleme (wie SAT-Instanzen) in QUBO-Formate führt oft zu einer enormen Anzahl an Variablen und großen Koeffizienten. Dies macht die Lösung auf aktuellen Quanten-Annealern (die oft auf ca. 30.000 logische Variablen beschränkt sind) unmöglich oder ineffizient.
• Kontext: Kryptografische Funktionen (z. B. AES, SHA, MD5) basieren auf komplexen booleschen Logikgattern. Die Inversion dieser Funktionen (z. B. zum Brechen von Verschlüsselungen) erfordert die Umwandlung in SAT-Formeln und deren anschließende Abbildung auf QUBO.
• Ziel: Die Reduktion der Anzahl der logischen Variablen und die Minimierung der Koeffizientenmagnituden in der QUBO-Matrix, um die Angriffsfläche für zukünftige Quantencomputer zu erhöhen und die Effizienz bestehender Solver zu steigern.

2. Methodik

Die Autoren entwickeln einen systematischen Ansatz zur Erstellung kompakter QUBO-Codierungen durch die Kombination von Integer Linear Programming (ILP) und der Analyse spezifischer SAT-Normalformen.

A. ILP-basierte Mustererkennung

Statt QUBO-Formeln manuell abzuleiten, nutzen die Autoren ein ILP-Verfahren, um optimale Abbildungen für kleine, handhabbare SAT-Instanzen zu finden.

• Ansatz: Sie definieren eine quadratische Funktion $g(x, s)$, die für gültige Min-Terme (erfüllte Belegungen) den Wert 0 annimmt und für alle anderen Belegungen (inkl. falscher Substitutionsvariablen $s$) einen Wert $>0$ liefert.
• Substitutionsvariablen: Das ILP sucht nach der minimalen Anzahl an zusätzlichen binären Variablen ($s$), die notwendig sind, um höhere Ordnungen (z. B. AND/OR/XOR mit vielen Eingängen) auf quadratische Terme zu reduzieren.
• Symmetriebrechung: Um den Suchraum zu verkleinern, werden Techniken wie Symmetriebrechung und schrittweises Hinzufügen von Nebenbedingungen (Counter-Example Guided Optimization) eingesetzt.

B. Theoretische Sätze und Codierungsstrategien

Basierend auf den ILP-Ergebnissen leiten die Autoren allgemeine Sätze und Formeln für verschiedene logische Strukturen ab:

1. Paritätskodierung (XOR): Für Multi-Input-XOR-Gatter wird eine Methode entwickelt, die auf der Darstellung ungerader Summen basiert. Dies ermöglicht eine effiziente Kodierung mit einer logarithmischen Anzahl an Substitutionsvariablen.
2. Root Squeezing Theorem & Range Encoding: Ein zentrales Ergebnis ist die Erkenntnis, dass Bereichsbeschränkungen (z. B. Multi-Input-OR oder Popcount) durch das Produkt zweier linearer Terme kodiert werden können, deren Nullstellen sich um höchstens 1 unterscheiden.
   • Formel: $(\sum x_i - f_1(s)) \cdot (\sum x_i - f_2(s))$.
   • Vorteil: Diese "Dualität" erlaubt es, zwei Werte gleichzeitig mit einem Substitutionsbit zu kodieren, was eine Reduktion der Variablenanzahl um genau ein Bit gegenüber herkömmlichen quadratischen Ansätzen ermöglicht.
3. Normalformen (CNF, DNF, ANF): Die Autoren zeigen, wie komplexe SAT-Formen durch die Kombination dieser Bausteine (XOR, OR, AND) effizient kodiert werden können, wobei Substitutionsvariablen als "Logik-Marker" für Zwischenergebnisse dienen.

3. Wichtige Beiträge

• Entwicklung kompakter Codierungsmuster: Die Einführung von Algorithmen, die die Anzahl der benötigten Substitutionsvariablen für gängige logische Gatter (insbesondere OR und XOR) minimieren.
• Root Squeezing Theorem: Ein mathematischer Beweis, der zeigt, wie Bereichsbeschränkungen mit minimalen Hilfsvariablen kodiert werden können.
• Anwendung auf Kryptografie: Die erfolgreiche Anwendung dieser Methoden auf reale, komplexe Kryptoalgorithmen (AES-128/192/256, MD5, SHA-1, SHA-256).
• Optimierung der S-Box für AES: Eine detaillierte Analyse und ILP-basierte Optimierung der Multiplikation und Inversion in endlichen Körpern ($GF(2^8)$), die den kritischen Engpass bei der AES-Kodierung darstellen.

4. Ergebnisse

Die Autoren demonstrieren ihre Methode an mehreren Kryptoalgorithmen und vergleichen die Ergebnisse mit früheren Veröffentlichungen (insbesondere Ref. [36], [35], [74]).

• AES-256: Die QUBO-Instanz wurde im Vergleich zu den besten bisher veröffentlichten Ergebnissen um den Faktor 8 reduziert.
  • Statt 250.000 Variablen benötigen die Autoren nur **31.242 Variablen** (für die Entschlüsselung).
  • Dies entspricht nur 12 % der Größe früherer Ansätze.
• AES-128/192: Ähnlich signifikante Reduktionen (auf 24 % bzw. 12 % der vorherigen Größen).
• Hash-Funktionen (MD5, SHA-1, SHA-256):
  • Für SHA-256 wurde eine Reduktion von ~47.808 auf 30.255 Variablen erreicht (bei Verwendung von Blockgröße $B=6$).
  • Für MD5 wurde eine Reduktion auf 10.272 Variablen erzielt.
• Matrix-Eigenschaften: Die resultierenden QUBO-Matrizen sind extrem dünn besetzt (Sparsity) (zwischen 0,04 % und 0,52 %), was für das Mapping auf Hardware mit begrenzter Konnektivität (wie Quanten-Annealer) von großem Vorteil ist.
• Koeffizienten: Durch die Verwendung von Block-Additionstechniken ($B=1$ vs. $B=6$) können die Koeffizientenmagnituden kontrolliert werden, was für Hardware mit begrenzter numerischer Präzision entscheidend ist.

5. Bedeutung und Ausblick

• Sicherheitsimplikationen: Die drastische Reduktion der QUBO-Größe erhöht die Verwundbarkeit aktueller Kryptoalgorithmen gegenüber zukünftigen Quanten-Annealern. Eine Instanz von ~30.000 Variablen liegt bereits im Bereich dessen, was zukünftige Quantenhardware bewältigen könnte.
• Allgemeine Anwendbarkeit: Die entwickelten Muster (Root Squeezing, Paritätskodierung) sind nicht auf Kryptografie beschränkt, sondern dienen als generische Bausteine für die Kodierung beliebiger kombinatorischer Optimierungsprobleme.
• Herausforderungen: Die Suche nach optimalen booleschen Schaltkreisen für komplexe Funktionen (wie Multiplikation in $GF(2^n)$) bleibt ein NP-schweres Problem. Die Autoren weisen darauf hin, dass weitere Verbesserungen der ILP-Methoden notwendig sind, um die Variablenanzahl für noch größere Funktionen weiter zu minimieren.
• Zukunft: Die Arbeit legt den Grundstein für effizientere Quanten-Angriffe auf Kryptografie und bietet gleichzeitig Werkzeuge für die Optimierung von Quantenalgorithmen im Allgemeinen.

Fazit: Das Papier stellt einen bedeutenden Fortschritt in der QUBO-Formulierung dar, indem es durch mathematisch fundierte, ILP-gestützte Mustererkennung die Komplexität kryptografischer Probleme auf ein Niveau reduziert, das für zukünftige Quantencomputer relevant wird.