Technisches Resümee: Wie man Microcrypt nicht baut

1. Problemstellung

Das Feld der Quantenkryptographie hat sich in letzter Zeit auf „Microcrypt“ konzentriert: die Konstruktion kryptographischer Primitiven (wie etwa Pseudozufallszustände (PRS), Pseudozufalls-Unitaries (PRU) und One-Way State Generator (OWSG)) basierend auf Annahmen, die schwächer sind als klassische Einwegfunktionen (OWF). Insbesondere suchen Forscher nach Primitiven, die selbst gegen Angreifer mit einer NP-Oracle sicher bleiben.

Obwohl mehrere Kandidat-Konstruktionen vorgeschlagen wurden (z. B. Hamiltonian Phase States, IQP-Gruppenaktionen und verschiedene Clifford-Monomial-Clifford-Architekturen), mangelte es an einer systematischen Kryptanalyse gegen NP-gestützte Angreifer. Eine zentrale Herausforderung besteht darin, zu bestimmen, ob diese Konstruktionen unbeabsichtigt die Existenz klassischer Einwegfunktionen implizieren, was sie für Microcrypt ungeeignet machen würde. Dieses Paper adressiert die Frage: Welche natürlichen Rezepte zum Bau von PRS und PRUs scheitern, weil sie Einwegfunktionen oder NP-Härte implizieren?

2. Methodik

Die Autoren entwickeln zwei primäre technische Frameworks, um Kandidat-Konstruktionen zu analysieren und zu brechen:

A. NP-gestützte Schatten-Tomographie berechenbarer Zustände

Die Autoren führen einen effizienten Algorithmus zum Lernen von Quantenzuständen unter Verwendung eines NP-Oracles ein.

• Berechenbare Zustände: Eine Familie von Zuständen $\{|\psi_k\rangle\}$ wird als berechenbar definiert, wenn unter Verwendung eines Schlüssels $k$ die Amplitude und Phase jedes Rechenbasis-Terms effizient klassisch berechnet werden kann.
• Die Angriffsstrategie: Der Algorithmus erfolgt in zwei Stufen:
  1. Basis-Verteilungs-Matching: Er misst Kopien des unbekannten Zustands in der Rechenbasis, um ein klassisches Transkript zu erhalten. Unter Verwendung eines NP-Oracles sucht er nach einem Kandidaten-Schlüssel $k_0$, dessen vorhergesagte Messverteilung die Likelihood des beobachteten Transkripts maximiert. Dies stellt einen Schlüssel wieder her, der die Größenverteilung des unbekannten Zustands approximiert.
  2. Phasenextraktion via Interferenz: Um die Phaseninformationen zu extrahieren, die Basis-Messungen verwerfen, konstruiert der Algorithmus einen „Referenzzustand“ $|\psi_{k_0}^+\rangle$ (den Zustand mit positiven Amplituden des Kandidaten-Schlüssels). Er führt dann ein kontrolliertes SWAP-Interferenzexperiment zwischen dem unbekannten Zustand und diesem Referenzzustand durch. Dies ermöglicht die Extraktion der relativen Phaseninformationen.
  3. Finale Schlüsselwiederherstellung: Der Algorithmus sammelt Stichproben aus dieser Interferenzverteilung und nutzt eine zweite NP-Abfrage, um einen Schlüssel $h$ zu finden, der die Likelihood dieser phasen-sensitiven Stichproben maximiert.
• Ergebnis: Für jede OWSG-Familie mit berechenbaren Zuständen kann ein Angreifer mit einem NP-Oracle den Generator (das Finden eines Schlüssels, der einen hoch-fidelity Zustand erzeugt) in Polynomialzeit invertieren.

B. NP-gestütztes Lernen von Unitaries (CMC-Angriff)

Die Autoren entwickeln einen spezifischen Angriff auf Unitary-Familien der Form $U_k = C_{2,k} M_k C_{1,k}$, wobei $C$ Clifford-Unitaries sind und $M$ eine Monomial-Schicht (Permutation mit Phasen) darstellt.

• Die Strategie: Der Angriff nutzt Bell-Zustands-Messungen. Durch Präparation eines Bell-Zustands $|\beta_{a,c}\rangle$, Anwendung des unbekannten Unitaries $U$ auf beide Register und Messung in der Bell-Basis erhält der Angreifer „Displacement“-Constraints (Verschiebungs-Beschränkungen).
• Clifford-Korrektur: Da die äußeren Schichten Clifford sind, kann der Angreifer klassisch berechnen, wie diese Schichten die Bell-Basis-Labels permutieren. Durch das klassische „Rückgängigmachen“ der Clifford-Schichten reduziert sich das Problem darauf zu prüfen, ob die beobachteten Verschiebungen konsistent mit der mittleren Monomial-Schicht $M_k$ sind.
• NP-Abfrage: Der Angreifer fragt ein NP-Oracle: „Existiert ein einzelner Schlüssel $h$ und ein Satz von Witness-Strings, die alle beobachteten Displacement-Constraints erklären?“
• Ergebnis: Für jede solche CMC-Konstruktion kann der NP-Angreifer das Unitary mit hoher Wahrscheinlichkeit von einem Haar-zufälligen Unitary unterscheiden und das Unitary lernen. Des Weiteren erlaubt die Search-to-Decision-Reduktion dem Angreifer, den Schlüssel zu lernen.

3. Zentrale Beiträge und Ergebnisse

A. Invertierung von berechenbaren OWSGs

Das Paper beweist, dass alle OWSG-Familien mit berechenbaren Zuständen in BQPNP invertierbar sind (Quanten-Polynomialzeit mit Zugriff auf ein NP-Oracle).

• Implikation für Einwegfunktionen: Wenn ein OWSG nicht nur berechenbar, sondern auch samplable ist (d. h. man kann unter Verwendung des Schlüssels effizient klassisch aus der Messverteilung des Zustands sampeln kann), dann impliziert die Existenz eines solchen OWSG die Existenz einer klassischen Einwegfunktion.
• Spezifische Brüche: Dieses Ergebnis bricht die Sicherheit von:
  • Hamiltonian Phase States (HPS): Die Autoren zeigen, dass diese, die zuvor als potenziell schwächer als OWF vermutet wurden, tatsächlich OWFs implizieren.
  • IQP Group-Action States: Die Hardness-Annahmen von Morimae und Xagawa zeigen, dass sie OWFs implizieren.

B. Brechen von Pseudozufalls-Unitaries (PRUs)

Das Paper demonstriert, dass viele prominente PRU-Architekturen gegen NP-gestützte Angreifer unsicher sind:

• PFC und C2PFC1: Konstruktionen, bei denen eine Permutation/Phasen-Schicht zwischen Cliffords eingebettet ist (z. B. $C_2 P F C_1$), können von Haar-Random unterschieden und gelernt werden.
• LRFC und Blocked Variants: Verschiedene Luby-Rackoff-Funktionskonstruktionen mit Clifford-Endpunkten sind gebrochen.
• Generalisierung: Der Angriff lässt sich auf jede Unitary-Familie anwenden, bei der die „mittlere“ Schicht monomial ist und die Endpunkte effizient beschreibbare Cliffords sind.

C. Identifikation überlebender Kandidaten

Das Paper listet explizit Konstruktionen auf, für die die aktuellen Techniken keinen Angriff liefern, und merkt an, dass diese weiterhin plausible (wenn auch unbewiesene) Wege für Microcrypt darstellen. Dazu gehören:

• Volle PRSS (Pseudorandom State Scrambler) Walks mit vielen Mixing-Runden.
• Lange Kac-Walks.
• Konstruktionen mit überlappenden Blöcken oder intermediären Cliffords zwischen Monomial-Schichten (z. B. die dritte Blocked-LRFC-Form).
• Hidden-Basis Hamiltonian Dynamics.

4. Bedeutung und Behauptungen

Die Autoren positionieren diese Arbeit als Etablierung von „Leitplanken“ für das Feld der Microcrypt. Ihre primären Behauptungen sind:

1. Systematische Kryptanalyse: Sie gehen über Ad-hoc-Angriffe hinaus und bieten eine allgemeine Methodik (NP-gestützte Schatten-Tomographie und CMC-Analyse) zur Evaluierung von Quanten-Kryptographie-Kandidaten.
2. No-Go-Resultate: Sie zeigen, dass eine große Klasse von „natürlichen“ Konstruktionen – insbesondere solche, die auf berechenbaren Amplituden oder Clifford-Monomial-Clifford-Architekturen beruhen – kein Microcrypt realisieren können, da sie unbeabsichtigt klassische Einwegfunktionen implizieren oder durch NP-Oracles gebrochen werden.
3. Richtung für zukünftige Forschung: Durch die Identifizierung der Architekturen, die scheitern, verengen sie den Suchraum für lebensfähige Microcrypt-Primitive. Es wird suggeriert, dass zukünftige Konstruktionen wahrscheinlich auf Annahmen basieren müssen, die plausibel außerhalb der Komplexitätsklasse NP liegen, und spezifische strukturelle Muster (berechenbare Amplituden, einfache Clifford-Monomial-Clifford-Formen) vermeiden müssen, die die Autoren als verwundbar gezeigt haben.

Das Paper schließt mit der Feststellung, dass die Landschaft der Microcrypt zwar noch offen ist, aber die „leicht erreichbaren Früchte“ der berechenbaren und samplablen Zustandskonstruktionen sowie der Standard-CMC-Unitary-Architekturen als Kandidaten für Kryptographie ohne Einwegfunktionen ausgeschlossen wurden.