Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

Dieser Beitrag schlägt einen neuartigen Ansatz vor, der die zirkulante Struktur linearer Schichten in der symmetrischen Kryptographie nutzt, um Transformationssequenzen zu konstruieren, wodurch heuristische Algorithmen im Vergleich zu bisherigen State-of-the-Art-Ergebnissen deutlich effizientere XOR-Anzahlen und Schaltungstiefen für Blockchiffren wie Whirlwind und AES erreichen können.

Das Wesentliche

Stellen Sie sich vor, Sie sind ein Meisterarchitekt, der versucht, eine komplexe Maschine mit einem bestimmten Satz von Lego-Steinen zu bauen. In der Welt der Kryptographie (der Wissenschaft der Geheimschriften) werden diese „Maschinen" lineare Schichten genannt, und sie sind die Arbeitspferde, die Daten verschlüsseln, um sie sicher zu halten.

Seit Jahren versuchen Architekten, diese Maschinen mit den fewest möglichen Steinen (um Platz zu sparen) und in der kürzesten möglichen Zeit (um Geschwindigkeit zu sparen) zu bauen. Das von Ihnen bereitgestellte Papier stellt eine neue Methode zur Konstruktion dieser Maschinen vor, indem es ein verborgenes Muster in den Bauplänen erkennt.

Hier ist die Aufschlüsselung ihrer Entdeckung, einfach erklärt:

1. Das Problem: Die „Mauer aus Ziegelsteinen" der Komplexität

Stellen Sie sich eine kryptographische lineare Schicht als eine massive Mauer aus Schaltern vor. Um eine Nachricht zu verschlüsseln, müssen Sie diese Schalter in einer sehr spezifischen Reihenfolge umlegen.

• Das Ziel: Sie möchten die Schalter mit den fewest Zügen umlegen (um Energie/Platz zu sparen) und in den fewest Schritten (um es schnell zu machen).
• Der alte Weg: Frühere Methoden behandelten die Mauer als ein riesiges, chaotisches Durcheinander von Schaltern. Sie verwendeten Trial-and-Error-Algorithmen, um die beste Reihenfolge zu finden, aber da die Mauer so groß und unordentlich war, verpassten sie oft den effizientesten Pfad. Es war, als würde man versuchen, ein Labyrinth zu lösen, indem man zufällig gegen Wände läuft.

2. Die Entdeckung: Das Muster des „drehenden Rades"

Die Autoren stellten fest, dass viele dieser kryptographischen Mauern tatsächlich nicht zufällig sind. Sie haben eine zirkuläre Struktur.

• Die Analogie: Stellen Sie sich ein Karussell vor. Wenn Sie ein Foto der Pferde machen und dann das Foto drehen, sieht das Muster der Pferde fast gleich aus, nur verschoben.
• In mathematischen Begriffen wird die Matrix (der Bauplan der Schalter) dadurch aufgebaut, dass eine einzelne Zeile immer wieder verschoben wird. Es ist ein sich wiederholendes, rotierendes Muster.
• Die Erkenntnis: Frühere Architekten ignorierten dieses „Karussell"-Muster und behandelten die Mauer als chaotisches Durcheinander. Die Autoren erkannten, dass man, wenn man das Muster anerkennt, die Mauer viel effizienter abbauen kann.

3. Die Lösung: Der „Falt"-Trick

Anstatt zu versuchen, die ganze riesige Mauer auf einmal zu lösen, entwickelten die Autoren eine Methode, um das Problem zu falten.

• Die Metapher: Stellen Sie sich vor, Sie haben eine riesige, schwere Steppdecke mit einem sich wiederholenden Muster. Anstatt zu versuchen, das ganze Ding auf einmal zu falten, erkennen Sie, dass Sie, da sich das Muster wiederholt, die linke Hälfte auf die rechte Hälfte falten können, dann die Oberseite auf die Unterseite.
• Durch die Verwendung dieser „Falt"-Technik (mathematische Transformation der Matrix) können sie eine massive, komplexe Mauer in eine viel einfachere, dreieckige Form verwandeln.
• Sobald die Mauer in diese dreieckige Form vereinfacht ist, können Standardwerkzeuge die Arbeit leicht abschließen. Es ist, als würde man einen verwickelten Wollknäuel in eine ordentliche, gerade Linie verwandeln, bevor man versucht, einen Knoten zu binden.

4. Die Ergebnisse: Schnellere und kleinere Maschinen

Die Autoren testeten diese neue „Falt"-Methode an realen kryptographischen Maschinen, die in populären Sicherheitssystemen verwendet werden. Die Ergebnisse waren beeindruckend:

• Die „Wirbelwind"-Maschine:

  • Geschwindigkeit: Sie reduzierten die Zeit, die zum Ausführen der Maschine benötigt wird, um 39 %. Stellen Sie sich ein Auto vor, das früher 28 Sekunden brauchte, um eine Meile zu fahren, und das dies nun in 17 Sekunden schafft.
  • Größe: Sie reduzierten die Anzahl der benötigten „Steine" (Logikgatter) um etwa 30 %. Das bedeutet, die Maschine ist kleiner und verbraucht weniger Energie.

• Die „AES"-Maschine (Der Goldstandard):

  • AES ist der berühmteste Verschlüsselungsstandard der Welt. Sein „MixColumn"-Teil ist ein berüchtigtes Rätsel, das effizient zu lösen schwierig ist.
  • Die Leistung: Die Autoren bauten ein automatisiertes System, das dieses Rätsel fast genauso gut löste wie ein menschlicher Experte, der wochenlang manuell am Design feilte.
  • Der Haken: Das Design des menschlichen Experten verwendete 105 „Steine". Das automatisierte Design der Autoren verwendete 107. Das sind nur 2 zusätzliche Steine für ein Ergebnis, das automatisch und nicht von Hand erreicht wurde. Sie erreichten auch den Rekord für die schnellste Geschwindigkeit (Tiefe).

5. Warum das wichtig ist

• Für die Zukunft: Da Computer leistungsfähiger werden (einschließlich Quantencomputer), müssen diese „Maschinen" schneller und kleiner sein, um sicher zu bleiben.
• Die Kernaussage: Indem sie einfach erkannten, dass der Bauplan ein sich wiederholendes, rotierendes Muster hat (wie ein Karussell), fanden die Autoren einen Shortcut, den frühere Methoden verpassten. Sie erfanden keinen neuen Steintyp; sie fanden nur einen intelligenteren Weg, sie zu stapeln.

Zusammenfassend: Das Papier sagt: „Wir haben festgestellt, dass viele Sicherheitscodes auf einem sich wiederholenden Muster aufgebaut sind. Indem wir dieses Muster nutzen, um das Design zuerst zu vereinfachen, können wir die Sicherheitssysteme schneller und kleiner bauen als je zuvor, und sogar einige der besten menschlichen Experten schlagen."

Technische Zusammenfassung

Technische Zusammenfassung: Nutzung der zirkulanten Struktur zur Optimierung der Implementierung linearer Schichten

Problemstellung
Die Optimierung linearer Schichten in der symmetrischen Kryptographie ist sowohl für leichte Implementierungen (eingeschränkt durch Gatteranzahl und Fläche) als auch für Sicherheitsbewertungen im Quantenkontext (eingeschränkt durch Schaltungstiefe und DW-Kosten) von entscheidender Bedeutung. Zwar existieren heuristische Algorithmen zur Synthese von CNOT-Schaltungen (Quanten) und XOR-Schaltungen (klassisch) für allgemeine invertierbare Matrizen, doch versäumen sie oft, spezifische algebraische Strukturen, die in kryptographischen Designs inhärent sind, vollständig auszunutzen. Viele weit verbreitete Matrizen, wie beispielsweise die in AES MixColumn und Whirlwind, besitzen eine zirkulante Struktur. Bestehende State-of-the-Art-Methoden, wie die von Shi und Feng [SF24], behandeln diese Matrizen als allgemeine $n \times n$-Binärmatrizen und verpassen dabei möglicherweise Chancen, die Schaltungstiefe und Gatteranzahl durch Ausnutzung ihrer zugrundeliegenden zirkulanten Eigenschaften zu reduzieren.

Methodik
Die Autoren schlagen ein neuartiges Framework vor, das die zirkulante Struktur von Matrizen explizit nutzt, um die Synthese effizienter Schaltungen zu steuern. Die Kernmethodik umfasst eine rekursive Zerlegungsstrategie, die eine zirkulante Matrix über einem Körpererweiterung (z. B. $F_{2^k}$ oder $GL(F_2, m)$) in eine einfachere Form, spezifisch eine obere Dreiecksmatrix, transformiert, bevor eine Standard-heuristische Optimierung angewendet wird.

Zu den wichtigsten technischen Komponenten gehören:

1. Rekursive Blocktransformation: Satz 3 stellt fest, dass eine $2^k \times 2^k$-zirkulante Matrix über $F_2[x]$ durch elementare Zeilen- und Spaltenoperationen in eine blockweise obere Dreiecksmatrix transformiert werden kann. Der Algorithmus teilt die Matrix rekursiv in Blöcke $A$ und $B$ auf (wobei $M = \begin{smallmatrix} A & B \\ B & A \end{smallmatrix}$), wendet Operationen an, um bestimmte Blöcke zu nullen (z. B. Transformation zu $\begin{smallmatrix} A+B & B \\ A+B & \dots \end{smallmatrix}$).
2. Exploration von Transformationspfaden: Die Autoren beobachten, dass unterschiedliche Wahlmöglichkeiten von Zeilen- und Spaltenoperationen während des rekursiven Schritts zu verschiedenen Zwischenmatrizen führen. Der Algorithmus (Algorithmus 1) erkundet mehrere Transformationspfade (bis zu $4^{2^k-1}$ Möglichkeiten für kleine $k$), um den Pfad zu finden, der die effizienteste nachfolgende Schaltung liefert.
3. Frühes Stoppen und Fallback: Unter Berücksichtigung, dass der Nutzen der Rekursion mit größerer Tiefe abnimmt, führen die Autoren eine Strategie (Algorithmus 2) ein, um die Rekursion frühzeitig zu beenden. Der Algorithmus iteriert durch verschiedene „Blockgrößen" und variiert damit effektiv die Rekursionstiefe. Wird die Rekursion frühzeitig gestoppt, wird die resultierende Matrix an einen Standard-heuristischen Optimierer (Heu) zur allgemeinen CNOT/XOR-Synthese übergeben. Dies umfasst eine „Fallback"-Strategie, bei der die Rekursionstiefe null ist und die Matrix effektiv als allgemeiner Fall behandelt wird.
4. Automatisierte Optimierung: Im Gegensatz zu früheren manuellen Ansätzen (z. B. Zhang et al. [ZSWS24] für AES) automatisiert diese Methode den Prozess des Findens der „einfacheren" Matrixform und der entsprechenden Gattersequenzen und eliminiert die Notwendigkeit menschlicher Eingriffe.

Hauptbeiträge

• Neuartiges Framework: Dies ist die erste Arbeit, die die zirkulante Struktur linearer Schichten systematisch nutzt, um Schaltungsimplementierungen zu optimieren und so die Lücke zwischen algebraischen Matrixeigenschaften und Schaltungssynthese-Heuristiken zu schließen.
• Automatisierte Synthese: Die Autoren stellen einen automatisierten Algorithmus bereit, der manuelle, fallbezogene Optimierungen ersetzt. Er erzeugt Sequenzen von Transformationsmatrizen, die nachgelagerten Heuristiken ermöglichen, effizientere Implementierungen zu finden.
• Duale Optimierung: Das Framework ist sowohl für Quantenschaltungen (Minimierung der CNOT-Anzahl und -Tiefe) als auch für klassische Schaltungen (Minimierung der XOR-Anzahl, spezifisch g-XOR und s-XOR) anwendbar.

Ergebnisse
Die Autoren bewerteten ihre Methode an einem Datensatz linearer Schichten aus Blockchiffren (einschließlich AES, Whirlwind, Clefia, PRIDE usw.) und konstruierten MDS-Matrizen.

• Quantenschaltungstiefe:

  • Whirlwind M0: Die vorgeschlagene Methode reduzierte die Schaltungstiefe von 28 (bisheriger State-of-the-Art durch [SF24]) auf 17, eine Verbesserung um 39 %. Auch die Gatteranzahl wurde von 286 auf 200 reduziert.
  • AES MixColumn: Die automatisierte Methode erreichte eine Tiefe von 10 und entsprach damit dem manuell optimierten State-of-the-Art-Ergebnis von Zhang et al. [ZSWS24]. Die Gatteranzahl betrug 107, was nur 2 CNOTs mehr als das manuelle Ergebnis (105) sind und deutlich besser als die 131 CNOTs, die von [SF24] erreicht wurden.
  • Andere Matrizen: Bei Matrizen mit hoher Dichte (z. B. Whirlwind, SKOP15 8x8) wurden signifikante Tiefenreduktionen beobachtet, während Verbesserungen bei dünnbesetzten Matrizen, bei denen Heuristiken bereits gut funktionieren, marginal oder nicht vorhanden waren.

• Klassische Schaltung (XOR-Anzahl):

  • Whirlwind M0: Die Methode erreichte eine s-XOR-Anzahl von 159 und übertraf damit den bisherigen Bestwert von 173 (Yuan et al. [YWS+24]) um etwa 8 %.
  • Allgemeine Leistung: Während die Methode bei vielen Matrizen generell einen Größenaufwand verursacht, gelang es ihr, State-of-the-Art-Ergebnisse für spezifische hochdichte Matrizen wie Whirlwind M0 und M1 zu übertreffen.

Bedeutung und Behauptungen
Die Arbeit behauptet, dass die Ausnutzung der zirkulanten Struktur ein leistungsfähiger, bisher untergenutzter Ansatz zur Optimierung linearer Schichten ist. Die Autoren versichern, dass ihr Ansatz:

1. Bestehende Heuristiken für bestimmte, dichte Matrizen übertrifft, bei denen Standard-Greedy-Strategien Schwierigkeiten haben.
2. Manuelle Optimierung automatisiert und Ergebnisse erzielt, die mit von menschlichen Experten abgestimmten Schaltungen vergleichbar sind (wie beim AES MixColumn zu sehen), ohne dass manuelle Eingriffe erforderlich sind.
3. Eine neue Basislinie für Quantensicherheitsbewertungen bietet, indem er genauere Tiefenschätzungen für lineare Schichten liefert, was für die Berechnung der DW-Kosten (Tiefe $\times$ Breite) bei Post-Quanten-Sicherheitsbewertungen entscheidend ist.

Die Autoren schließen, dass die Methode zwar nicht universell für alle Matrixtypen überlegen ist (insbesondere für dünnbesetzte), aber einen signifikanten Vorteil für Matrizen mit zirkulanten Strukturen und hoher Dichte bietet und damit das Potenzial zeigt, algebraische Eigenschaften in die Schaltungssynthese zu integrieren.