A NISQ-friendly Coined Quantum Walk Algorithm for Chaos-based Cryptographic Applications

Die Arbeit stellt einen lackadaisischen alternierenden Quantenwalk (LAQW) vor, der durch eine signifikant reduzierte Schaltungstiefe im Vergleich zum bestehenden CAQW-Modell für NISQ-Geräte geeignet ist und dessen Eignung für die Erzeugung reproduzierbarer kryptografischer Schlüssel unter simuliertem Rauschen demonstriert wird.

Das Wesentliche

Das große Problem: Der verrückte Quanten-Tanz

Stell dir vor, du hast einen kleinen Roboter (den „Walker"), der auf einem riesigen Schachbrett (dem Gitter) tanzt. In der klassischen Welt würde dieser Roboter einfach zufällig nach links oder rechts springen, wie ein Betrunkener, der nach Hause torkelt. Das nennt man einen „Zufallsspaziergang".

In der Quantenwelt ist das aber viel verrückter. Der Roboter kann gleichzeitig nach links, rechts und sogar stehen bleiben. Er nutzt die Gesetze der Quantenmechanik, um sich zu bewegen. Das Ergebnis ist ein extrem chaotisches Muster, das man kaum vorhersagen kann. Genau diese Unvorhersehbarkeit ist Gold wert für Verschlüsselung. Wenn du ein Geheimnis (einen Schlüssel) verschlüsseln willst, brauchst du etwas, das so chaotisch ist, dass ein Hacker es nicht erraten kann.

Das alte Problem: Der Tanz war zu anstrengend

Bisher gab es eine Methode, diesen Quanten-Tanz zu programmieren, die man CAQW nannte. Stell dir das wie einen Tanzkurs vor, bei dem der Lehrer (der Computer) für jeden einzelnen Schritt des Tänzers eine neue, komplizierte Anweisung geben muss.

• Das Problem: Je länger der Tanz (mehr Zeitstufen) und je größer das Schachbrett, desto mehr Anweisungen muss der Lehrer geben.
• Die Folge: Die heutigen Quantencomputer (die sogenannten NISQ-Geräte) sind noch sehr fehleranfällig und haben wenig Geduld. Wenn der Tanz zu lange dauert (zu viele Schritte), vergisst der Computer die Anweisungen oder macht Fehler. Das Ergebnis ist dann kein sauberer Tanz mehr, sondern ein lausiges Geplapper. Für eine sichere Verschlüsselung ist das katastrophal, denn Sender und Empfänger müssen exakt denselben Tanz tanzen, um den Schlüssel zu finden.

Die neue Lösung: Der „Lackadaisical" (Gelassene) Tanz

Die Autoren dieses Papiers haben eine clevere Idee entwickelt: Sie nennen es LAQW (Lackadaisical Alternating Quantum Walk). „Lackadaisical" bedeutet auf Deutsch so viel wie „gelassen" oder „entspannt".

Die Metapher:
Stell dir vor, der alte Tanz (CAQW) war wie ein Marathon, bei dem der Läufer bei jedem Schritt über ein Hindernis springen muss. Das ist anstrengend und führt schnell zur Erschöpfung (Fehler im Computer).

Der neue Tanz (LAQW) ist anders:

1. Selbstschleifen: Jeder Punkt auf dem Schachbrett hat jetzt eine kleine „Rastbank" (eine Schleife). Der Tänzer kann entscheiden: „Ich gehe links", „Ich gehe rechts" oder „Ich bleibe einfach hier sitzen und trinke einen Kaffee."
2. Der Trick: Durch diese Möglichkeit, stehen zu bleiben, verändert sich die Mathematik dahinter. Der Computer muss nicht mehr für jeden einzelnen Schritt eine riesige, komplizierte Rechnung anstellen. Er kann den Tanz viel effizienter organisieren.

Das Ergebnis:
Der neue Tanz ist 88 % kürzer als der alte!

• Alt: Der Computer musste 100 Schritte machen, um ein Ergebnis zu bekommen.
• Neu: Der Computer braucht nur noch 12 Schritte für das gleiche Ergebnis.

Das ist wie der Unterschied zwischen einem alten, schweren Dampflokomotiv und einem modernen Hochgeschwindigkeitszug. Beide kommen ans Ziel, aber der Zug braucht viel weniger Energie und Zeit. Das macht den neuen Algorithmus perfekt für die heutigen, noch etwas „nervösen" Quantencomputer.

Wie wird daraus ein Geheimschlüssel?

Der Tanz allein reicht nicht. Man muss das Ergebnis in einen Schlüssel verwandeln.

1. Der Tanz: Der Quanten-Roboter tanzt und landet am Ende an verschiedenen Positionen auf dem Brett.
2. Die Messung: Wir zählen, wie oft er wo gelandet ist. Das ist wie ein Wurf mit einem sehr seltsamen, quantenmechanischen Würfel.
3. Die Verarbeitung (Post-Processing): Da Quantencomputer manchmal kleine Fehler machen (Rauschen), ist das Ergebnis nicht perfekt. Die Autoren haben eine Art „Filter" entwickelt (sie nennen es „Primzahl-Modulus-Mapping"). Stell dir das wie einen Sieb vor, das die unregelmäßigen Körner (Fehler) herausfiltert und nur die perfekten, glatten Steine (zufällige Bits) durchlässt.
4. Der Schlüssel: Am Ende haben Sender und Empfänger, die denselben Tanz mit denselben Startparametern getanzt haben, exakt denselben 128-Bit-Schlüssel. Ein Hacker, der nur eine winzige Abweichung in den Startparametern hat, bekommt einen völlig anderen, nutzlosen Schlüssel.

Warum ist das wichtig?

• Sicherheit: Der neue Tanz ist so chaotisch, dass er extrem schwer zu knacken ist.
• Praktikabilität: Weil der Tanz so viel kürzer ist, können wir ihn heute schon auf echten Quantencomputern ausprobieren, ohne dass der Computer vor Erschöpfung zusammenbricht.
• Zuverlässigkeit: Selbst wenn der Computer ein bisschen „nervös" ist (Rauschen), funktioniert der neue Tanz immer noch so gut, dass Sender und Empfänger denselben Schlüssel erhalten.

Zusammenfassend:
Die Forscher haben einen Weg gefunden, wie man Quantencomputer nutzen kann, um extrem sichere Schlüssel zu generieren, ohne dass die Computer dabei „verrückt" werden. Sie haben den Tanz vereinfacht, indem sie dem Tänzer erlaubt haben, Pausen zu machen, und dadurch die ganze Show so effizient gemacht, dass sie auf der aktuellen Hardware funktioniert. Das ist ein wichtiger Schritt hin zu einer Zukunft, in der unsere Daten durch Quantenphysik geschützt sind.

Technische Zusammenfassung

1. Problemstellung

Das Paper adressiert die Herausforderung, Quanten-zufallsbasierte Kryptographie-Verfahren auf aktuellen NISQ-Geräten (Noisy Intermediate-Scale Quantum) zu implementieren.

• Hintergrund: Diskrete zeitliche Quantenwalks (DTQWs) sind chaotische Systeme, die aufgrund ihrer Sensitivität gegenüber Anfangsbedingungen und ihrer Fähigkeit, große Pseudorandom-Schlüssel aus kleinen Geheimnissen zu generieren, für symmetrische Verschlüsselung geeignet sind.
• Das Problem: Bestehende Modelle wie der Controlled Alternating Quantum Walk (CAQW), der in Bildverschlüsselung und Hash-Funktionen verwendet wird, erfordern Quantenschaltkreise mit einer Tiefe, die sich quadratisch mit der Gittergröße ($n$) und linear mit der Anzahl der Zeitschritte ($t$) skaliert: $O(n^2 t)$.
• Folge: Diese hohe Schaltkreistiefe führt zu einer hohen Gate-Anzahl und langen Ausführungszeiten, was auf NISQ-Hardware aufgrund von Dekohärenz und Gate-Fehlern zu unbrauchbaren, nicht reproduzierbaren Ergebnissen führt. Zudem erfordern CAQW-Modelle für eine korrekte Wahrscheinlichkeitsverteilung ungerade Gittergrößen, was die Implementierung mit Qubits (die $2^n$-Dimensionen haben) erschwert.

2. Methodik

Die Autoren stellen ein neues Modell vor: den Lackadaisical Alternating Quantum Walk (LAQW).

• Das LAQW-Modell:

  • Es basiert auf dem Konzept des Lackadaisical Quantum Walks (LQW), bei dem jedem Knoten des Graphen eine Selbstschleife (self-loop) hinzugefügt wird.
  • Dies ermöglicht dem „Walker", an einem Ort zu verbleiben, anstatt sich nur zu bewegen.
  • Vorteil: Durch die Selbstschleifen können gerade Gittergrößen ($2n \times 2n$) verwendet werden, ohne dass die Wahrscheinlichkeitsverteilung auf nur die Hälfte der Knoten beschränkt bleibt (ein bekanntes Problem bei CAQW auf geraden Graphen).
  • Schaltkreis-Optimierung: Die Verschiebungsoperatoren (Shift Operators) werden so definiert, dass sie circulante Matrizen ergeben. Dies ermöglicht die Nutzung des Quantum Fourier Transform (QFT)-Ansatzes zur Implementierung der Verschiebungen.
  • Komplexitätsreduktion: Durch den QFT-Ansatz skaliert die Schaltkreistiefe des LAQW nur noch als $O(n^2 + nt)$, im Vergleich zu $O(n^2 t)$ beim CAQW.

• Schlüsselgenerierungs-Schema:

  1. Messung: Der LAQW wird über viele „Shots" ($\approx 10^6$) ausgeführt, um eine Wahrscheinlichkeitsverteilung zu erhalten.
  2. Post-Processing:
     • Rundung: Zählwerte werden deterministisch in Intervalle gerundet, um Reproduzierbarkeit trotz statistischer Schwankungen zu gewährleisten.
     • Prime-Modulus-Mapping: Die gerundeten Werte werden unter Verwendung einer Liste von Primzahlen auf Byte-Werte (0–255) abgebildet, um eine gleichmäßige Verteilung zu erzwingen und die zugrundeliegende Struktur zu brechen.
  3. Entropie-Schätzung & Extraktion:
     • Die Min-Entropie wird konservativ basierend auf der maximalen Wahrscheinlichkeit eines Ergebnisses geschätzt (unter Verwendung des Clopper-Pearson-Intervalls).
     • Unter Anwendung des Leftover Hash Lemma (LHL) wird eine deterministische, gewichtete Bit-Extraktion durchgeführt, um einen fast-uniformen symmetrischen Schlüssel (z. B. 128 Bit) zu generieren.

3. Wichtige Beiträge

1. Entwurf des LAQW: Einführung eines neuen Quantenwalk-Modells, das für NISQ-Geräte optimiert ist und gerade Gittergrößen unterstützt.
2. Schaltkreis-Implementierung: Demonstration einer Quantenschaltung, die eine signifikante Reduktion der Tiefe erreicht, indem QFT-basierte Verschiebungsoperatoren genutzt werden.
3. Kryptographisches Protokoll: Entwicklung eines vollständigen, reproduzierbaren Protokolls zur Generierung symmetrischer Schlüssel aus Quantenmessdaten unter Berücksichtigung von Rauschen und Entropie-Boundaries.
4. Umfassende Evaluation: Vergleich mit dem CAQW-Modell hinsichtlich Schaltkreistiefe, Parameter-Sensitivität, statistischer Zufälligkeit (NIST-Tests) und Robustheit gegenüber Hardware-Rauschen.

4. Ergebnisse

• Schaltkreistiefe: Der LAQW erreicht eine durchschnittliche Reduktion der Schaltkreistiefe von ca. 88 % im Vergleich zum CAQW (z. B. bei $t=20$ und $8 \times 8$ Gitter: 550 Gates vs. 5064 Gates beim CAQW auf einem Simulator). Dies macht LAQW deutlich praktikabler für aktuelle Hardware.
• Parameter-Sensitivität (Chaos-Eigenschaft):
  • Der LAQW ist sensibler gegenüber kleinen Änderungen der Coin-Parameter ($\theta_0, \theta_1, \alpha$) als der CAQW (höhere Hellinger-Distanzen).
  • Der CAQW ist jedoch empfindlicher gegenüber Änderungen der Zeitschritte ($t$).
  • Bei völlig unterschiedlichen Anfangsparametern zeigt der CAQW eine etwas höhere mittlere Hellinger-Distanz (mehr „Zufälligkeit" zwischen unkorrelierten Sets), was einen Trade-off zwischen Schaltkreistiefe und maximaler Entropie aufzeigt.
• Statistische Tests (NIST SP 800-22):
  • Die generierten Schlüssel (128 Bit) bestehen fast alle NIST-Tests (Frequency, Block Frequency, Runs, etc.) mit hohen p-Werten ($p \ge 0.01$).
  • Der CAQW scheiterte am Block Frequency Test (lokale Ungleichgewichte), während der LAQW am Runs Test (zu häufige Alternierung) scheiterte, was jedoch durch die Extraktion des Schlüssels korrigiert wurde.
• Reproduzierbarkeit:
  • Unter idealen Bedingungen (Simulator) und unter realistischem Rauschen (IBM FakeTorino Backend) wurden die 128-Bit-Schlüssel mit extrem hoher Übereinstimmung reproduziert (Hamming-Distanz $\approx 0$).
  • Selbst bei Rauschen blieb die Anzahl extrahierbarer Bits stabil ($m_{max} \approx 1644$), und die Schlüssel waren in 99 % der Fälle identisch.
• Rauschresistenz: Das Schema erwies sich als robust gegenüber den Rauschmodellen des IBM Torino Backends; die Schlüsselgenerierung blieb funktionsfähig.

5. Bedeutung und Fazit

Das Paper demonstriert, dass die Nutzung von Quantenwalks für kryptographische Anwendungen auf aktuellen NISQ-Hardware-Plattformen machbar ist, wenn die Schaltkreistiefe optimiert wird.

• Praktische Relevanz: Die drastische Reduktion der Schaltkreistiefe ($O(n^2 + nt)$ statt $O(n^2 t)$) ist ein entscheidender Schritt, um Quanten-basierte Zufallsgeneratoren und Verschlüsselungsalgorithmen von theoretischen Modellen auf reale, fehleranfällige Prozessoren zu übertragen.
• Sicherheit: Das vorgeschlagene Schema bietet hohe Sensitivität gegenüber Anfangsparametern (wichtig gegen Brute-Force-Angriffe) und garantiert durch den Einsatz von Min-Entropie-Schätzungen und dem Leftover Hash Lemma die statistische Gleichverteilung der Schlüssel.
• Ausblick: Die Autoren betonen, dass die Optimierung der Abbildung von Wahrscheinlichkeitsverteilungen zu Schlüsseln und das Management der Trade-offs zwischen Reproduzierbarkeit und Sensitivität weitere Forschungsarbeiten erfordern, um die volle Leistungsfähigkeit in Anwendungen wie der Bildverschlüsselung auszuschöpfen.

Zusammenfassend stellt der LAQW einen vielversprechenden, hardware-freundlichen Ersatz für etablierte CAQW-Modelle in der chaosbasierten Kryptographie dar.