Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model

Dieses Paper stellt ein einfaches, simulations-sicheres One-Time-Memory-Schema im Quanten-Zufallsorakel-Modell vor, das ausschließlich auf einzelnen Wiesner-Zuständen und Konjunktionsoberfizierung basiert und eine plausible Sicherheit gegen quantenmechanische Angreifer mit begrenzter und adaptiver Tiefe gewährleistet.

Das Wesentliche

Das große Ziel: Ein Programm, das nur einmal lebt

Stellen Sie sich vor, Sie haben ein geheimes Rezept für den perfekten Kuchen. Sie wollen es jemandem geben, damit er ihn backen kann. Aber Sie haben Angst: Wenn er das Rezept einmal hat, könnte er es kopieren und an alle weitergeben.

In der klassischen Welt (Computer, Papier) ist es fast unmöglich, ein solches „Einmal-Rezept" zu schaffen, das nicht kopiert werden kann. In der Quantenwelt (mit Quantencomputern) ist es noch schwieriger, weil Quanteninformation sehr empfindlich ist.

Lev Stambler hat nun einen Weg gefunden, wie man ein solches „Einmal-Speicher-Gerät" (One-Time Memory) baut, das selbst gegen moderne Quantencomputer sicher ist – aber nur unter einer wichtigen Bedingung: Der Angreifer darf nicht unendlich lange und komplex rechnen können.

Die drei Geheimzutaten

Um dieses „Einmal-Rezept" zu bauen, nutzt die Arbeit drei einfache Zutaten, statt komplizierter Quanten-Magie:

1. Die „Wiesner-Zettel" (Einzelne Quanten-Bits):
   Stellen Sie sich vor, Sie schreiben das Rezept auf viele kleine Zettel. Jeder Zettel ist ein Quanten-Bit. Das Besondere: Jeder Zettel ist völlig unabhängig von den anderen. Es gibt keine „Verschränkung" (keine magische Verbindung zwischen den Zetteln). Das macht das System sehr robust und einfach herzustellen.

   • Der Trick: Jeder Zettel kann in zwei verschiedenen Farben geschrieben sein (z. B. Rot oder Blau). Wenn man ihn in der falschen Farbe liest, wird der Text unlesbar.

2. Der „Verschlüsselte Schlüssel" (Obfuscation):
   Um zu wissen, welche Farbe (Rot oder Blau) auf welchem Zettel steht, braucht man einen Schlüssel. Dieser Schlüssel ist in einem verschlüsselten Schloss (einem „Obfuscator") versteckt. Nur wer die richtigen Farben auf den richtigen Zetteln gemessen hat, kann das Schloss öffnen und den Schlüssel erhalten.

3. Der „Magische Zufallsgenerator" (Random Oracle):
   Das ist wie ein unvorhersehbarer Richter, der sofort entscheidet, ob eine Antwort richtig ist. Er zwingt den Angreifer, sich festzulegen, bevor er weitermachen kann.

Wie funktioniert der Trick? (Die Analogie)

Stellen Sie sich vor, Sie geben dem Empfänger einen Koffer mit 100 Zetteln.

• Auf 50 Zetteln steht das Rezept in Rot.
• Auf den anderen 50 steht das Rezept in Blau.
• Niemand weiß, welche Zettel welche Farbe haben.

Der Empfänger muss sich entscheiden: Will er die Rot-Zettel lesen oder die Blau-Zettel?

• Wenn er Rot misst: Er bekommt die richtigen Werte für die Rot-Zettel. Aber durch die Gesetze der Quantenphysik wird das, was auf den Blau-Zetteln stand, sofort „verwackelt" und unlesbar. Er kann das Blau-Rezept nicht mehr erraten.
• Wenn er Blau misst: Umgekehrt wird das Rot-Rezept unlesbar.

Das Problem: Ein sehr starker Quantencomputer könnte theoretisch versuchen, beide Farben gleichzeitig zu erraten, indem er die Zettel auf eine sehr clevere Weise „abtastet".

Die Lösung von Stambler:
Die Arbeit beweist ein neues mathematisches Gesetz (die POVM-Grenze):

„Wenn du versuchst, die Rot-Zettel fast perfekt zu lesen, ist die Wahrscheinlichkeit, dass du gleichzeitig die Blau-Zettel errätst, so gering, dass es praktisch unmöglich ist."

Es ist wie ein Würfelwurf: Wenn du versuchst, eine 6 zu werfen, ist die Chance, dass du gleichzeitig eine 1 würfelst, verschwindend gering. Je mehr Zettel (Bits) du hast, desto unmöglicher wird es, beide Seiten zu gewinnen.

Warum ist das sicher gegen Quantencomputer?

Ein normaler Quantencomputer könnte versuchen, die Zettel in einer Superposition (gleichzeitig Rot und Blau) zu halten. Aber hier kommt die zweite Bedingung ins Spiel: Begrenzte Rechengeschwindigkeit (Tiefe).

Stambler geht davon aus, dass ein Angreifer zwar viele Runden lang rechnen darf, aber in jeder einzelnen Runde nur eine begrenzte Anzahl von Quanten-Schritten machen kann (wie ein Computer, der nicht zu viele Operationen hintereinander ausführen kann, ohne dass das Signal verrauscht).

Die Arbeit nutzt ein theoretisches Werkzeug (das „Lifting-Theorem"), um zu argumentieren:

„Wenn ein Angreifer nicht tief genug in die Quanten-Matrix vordringen kann, um alle Zettel gleichzeitig perfekt zu analysieren, dann verhält er sich im Grunde wie ein klassischer Angreifer, der nur zufällig tippt."

Da die Wahrscheinlichkeit, beide Seiten zu knacken, bei vielen Zetteln astronomisch gering ist, bleibt das System sicher.

Warum ist das wichtig für die Zukunft?

1. Einfachheit: Frühere Versuche brauchten extrem komplexe Quanten-Verwicklungen, die wir heute noch gar nicht bauen können. Stamblers Idee braucht nur einfache, einzelne Quanten-Bits. Das könnte schon bald mit heutiger Hardware funktionieren.
2. Langlebigkeit: Da die Zettel nicht stark verwickelt sind, sind sie weniger anfällig für Fehler. Man könnte diese „Einmal-Programme" theoretisch in einem Quanten-Speicher lagern und später abrufen, ohne dass sie sofort kaputtgehen.
3. Sicherheit: Es bietet einen Weg, digitale Inhalte (wie Software-Lizenzen oder geheime Nachrichten) so zu verschlüsseln, dass sie wirklich nur einmal genutzt werden können, selbst wenn der Angreifer über einen Quantencomputer verfügt.

Zusammenfassung in einem Satz

Lev Stambler hat einen einfachen Weg gefunden, digitale „Einmal-Rezepte" zu bauen, die so sicher sind, dass selbst ein Quantencomputer sie nicht kopieren kann, solange er nicht unendlich schnell und tief rechnen darf – und das alles mit einfachen Bausteinen, die wir bald bauen können.

Technische Zusammenfassung

1. Problemstellung

Ein-Programme (One-Time Programs, OTPs) sind ein kryptographisches Primitive, das es erlaubt, ein Programm nur einmal auszuführen. Nach der Einführung durch Goldwasser, Kalai und Rothblum [10] wurde gezeigt, dass OTPs im Standardmodell (ohne zusätzliche Annahmen) nicht sicher konstruiert werden können.

In der Quantenwelt stellt sich die Herausforderung, wie man OTPs gegen Quantenangreifer absichert, die über Quantenspeicher verfügen. Bisherige Ansätze erfordern oft starke Annahmen wie:

• Hardware-Tokens (schwer zu implementieren, anfällig für Fehler).
• Isolierte Qubits oder begrenzte Quantenspeicher (physikalisch motiviert, aber einschränkend für die Nutzbarkeit).
• Indistinguishability Obfuscation (iO) oder komplexe Verschränkungszustände (schwer zu realisieren).

Ein zentrales Problem ist die Balance zwischen der Fähigkeit des Empfängers, den Quantenzustand für eine spätere Nutzung zu speichern, und der Sicherheit gegen Angreifer, die Quantenberechnungen durchführen können. Viele bestehende Modelle schränken den Angreifer so stark ein (z. B. durch Messung innerhalb einer festen Zeit), dass die praktische Anwendbarkeit von OTPs leidet.

Das Ziel dieses Papers ist die Konstruktion von simulations-sicheren One-Time Memories (OTMs) (die implizit OTPs ermöglichen), die:

1. Einfach und mit naher Zukunftstechnologie (Near-Term Hardware) realisierbar sind.
2. Sich gegen Angreifer mit begrenzter, aber adaptiver Quantentiefe (bounded adaptive quantum depth) schützen.
3. Keine komplexe Verschränkung oder iO benötigen.

2. Methodik und Modell

Die Arbeit basiert auf drei Hauptkomponenten:

A. Das Angreifermodell: $\mathsf{BPPQNCBQP}_d$

Statt Angreifer mit unbegrenzter Quantenleistung oder solchen, die zwischen Runden messen müssen, betrachtet das Paper Angreifer aus der Komplexitätsklasse $\mathsf{BPPQNCBQP}_d$ (definiert von Arora et al. [1]).

• Struktur: Der Angreifer führt adaptive Runden aus, wobei jede Runde aus einer Sequenz von polynomial vielen klassischen Berechnungen ($A_i$) und Quantenschaltungen mit begrenzter Tiefe $d$ ($Q_i$) besteht.
• Einschränkung: Die Quantentiefe zwischen den Oracle-Abfragen ist durch ein Polynom in der Sicherheitsparameter $\lambda$ begrenzt.
• Physikalische Motivation: Ohne Fehlerkorrektur (Fault Tolerance) akkumuliert Rauschen mit der Schaltungstiefe. Daher ist die kohärente Verarbeitungsfähigkeit eines Angreifers für nicht-fehlertolerant codierte Zustände physikalisch begrenzt. Dies erlaubt es dem Empfänger, den OTP im Quantenspeicher zu halten, ohne dass ein Angreifer mit begrenzter Tiefe ihn brechen kann.

B. Kryptographische Bausteine

1. Wiesner-Zustände (Conjugate Coding): Anstelle komplexer Verschränkung werden nur Tensorprodukte unabhängiger Ein-Qubit-Zustände verwendet. Jeder Zustand kodiert ein Geheimnis $s_i$ entweder in der $Z$-Basis (computational) oder $X$-Basis (Hadamard).
2. Konjunktion-Obfuskation (Conjunction Obfuscation): Basierend auf der Learning Parity with Noise (LPN) Annahme. Dies erlaubt es, zu verbergen, welche Positionen zu welcher Basis gehören, ohne dass der Angreifer die Schlüssel extrahieren kann, bevor er die korrekten Messergebnisse liefert.
3. Random Oracle Model (ROM): Eine ideale Hash-Funktion $\mathcal{H}$ wird verwendet, um Messergebnisse an die Konjunktionen zu binden.

C. Der „Lifting"-Ansatz

Die Sicherheit wird zunächst für Angreifer bewiesen, die nur klassische Abfragen an den Random Oracle stellen dürfen. Anschließend wird ein informeller „Lifting"-Argumentationsgang (basierend auf Arora et al. [1]) verwendet, um zu behaupten, dass diese Sicherheit auf Angreifer mit begrenzter Quantentiefe übertragbar ist. Die Idee ist, dass Angreifer mit begrenzter Tiefe keine kohärenten Superpositionen über viele Oracle-Abfragen hinweg aufrechterhalten können, ohne den Zustand zu kollabieren.

3. Schlüsselbeiträge und Technische Ergebnisse

A. Neue POVM-Schranke (Theorem 3.1)

Der theoretische Kern der Arbeit ist ein neuer informationstheoretischer Bound für konjugiertes Kodieren mit $m$ Qubits.

• Aussage: Wenn eine Messung (POVM) die Wahrscheinlichkeit $1-\epsilon$ hat, Zustände in der $Z$-Basis korrekt zu identifizieren, dann ist die Wahrscheinlichkeit, den in der konjugierten $X$-Basis kodierten String zu erraten, höchstens $\frac{1}{2^m} + O(\epsilon^{1/4})$.
• Besonderheit: Diese Schranke ist sequentiell. Das bedeutet, sie gilt auch dann, wenn der Angreifer erst misst und danach erfährt, in welcher Basis er hätte raten müssen. Dies generalisiert frühere Ein-Qubit-Ergebnisse auf den Multi-Qubit-Fall und zeigt, dass das Messen in einer Basis die Information in der konjugierten Basis exponentiell zerstört (hohe Min-Entropie).

B. Konstruktion des One-Time Memory (OTM)

Das Schema (Scheme 2) funktioniert wie folgt:

1. Vorbereitung: Der Sender erzeugt $n$ unabhängige Wiesner-Zustände. Eine zufällige Teilmenge $\Theta_X$ wird in $X$-Basis kodiert, die Komplementmenge $\Theta_Z$ in $Z$-Basis.
2. Verschlüsselung: Für jede Position wird ein Hash $h_i = \mathcal{H}(i, s_i)$ berechnet.
3. Obfuskation: Zwei Konjunktionen $\mathcal{O}_X$ und $\mathcal{O}_Z$ werden erstellt. Jede prüft, ob die eingegebenen Hashes für ihre jeweilige Teilmenge ($\Theta_X$ bzw. $\Theta_Z$) mit den gespeicherten Werten übereinstimmen. Bei Erfolg geben sie einen Schlüssel $k_\alpha$ zurück.
4. Nachrichten: Die eigentlichen Nachrichten $m_X, m_Z$ werden als $c_\alpha = k_\alpha \oplus m_\alpha$ verschlüsselt ausgegeben.
5. Auswertung: Der Empfänger misst den Zustand in der gewünschten Basis $\alpha$. Nur wenn er die korrekten Messergebnisse für die Positionen in $\Theta_\alpha$ liefert, kann er die Hashes berechnen, die Konjunktion $\mathcal{O}_\alpha$ evaluieren, den Schlüssel $k_\alpha$ erhalten und $m_\alpha$ entschlüsseln.

C. Sicherheitsbeweis (Klassische Abfragen)

Unter der LPN-Annahme und im Random Oracle Modell wird bewiesen, dass ein Angreifer, der nur klassische Abfragen an $\mathcal{H}$ stellt, nicht beide Nachrichten gleichzeitig erhalten kann.

• Um eine Konjunktion zu aktivieren, muss der Angreifer für alle Positionen der entsprechenden Basis die korrekten Hashes liefern.
• Aufgrund der POVM-Schranke (Theorem 3.1) führt eine erfolgreiche Messung in der $Z$-Basis dazu, dass die Information über die $X$-Basis (und damit die Hashes für $\Theta_X$) so stark gestört ist, dass das Raten der Hashes mit vernachlässigbarer Wahrscheinlichkeit gelingt.
• Da die Hashes klassisch abgefragt werden müssen, „verpflichtet" sich der Angreifer durch die Abfrage zu einem spezifischen Messergebnis.

D. Lifting auf Quantentiefe (Theorem 5.1 / Conjecture)

Die Autoren argumentieren, dass die Sicherheit gegen klassische Abfragen auf Angreifer mit begrenzter Quantentiefe übertragbar ist. Da Angreifer mit begrenzter Tiefe keine kohärenten Quantenabfragen über den Random Oracle hinweg durchführen können (ohne den Zustand zu kollabieren), reduziert sich ihr Verhalten effektiv auf klassische Transkripte. Dies ermöglicht die Anwendung des klassischen Sicherheitsbeweises.

4. Ergebnisse und Signifikanz

• Einfachheit und Praktikabilität: Das Schema benötigt nur Ein-Qubit-Operationen (Wiesner-Zustände) und klassisch instantiierbare Obfuskation (LPN-basiert). Es erfordert keine komplexe Verschränkung oder Indistinguishability Obfuscation (iO), was es für die Implementierung auf aktueller und naher Zukunftshardware (NISQ-Ära) vielversprechend macht.
• Robustheit gegen adaptive Angreifer: Im Gegensatz zu Modellen, die eine sofortige Messung erzwingen, erlaubt dieses Schema dem Empfänger, den Quantenzustand zu speichern und später zu nutzen. Die Sicherheit bleibt gegen Angreifer bestehen, die zwar adaptive Runden durchführen, deren Quantenverarbeitungstiefe jedoch physikalisch begrenzt ist (durch Rauschen ohne Fehlerkorrektur).
• Neue theoretische Grenzen: Die neue POVM-Schranke für sequentielle Messungen in konjugierten Basen ist ein eigenständiger theoretischer Fortschritt, der über frühere Ein-Qubit-Ergebnisse hinausgeht.
• Zukunftsperspektive: Die Arbeit ebnet den Weg für „echte" One-Time-Programme, die in Quantenspeichern persistieren können, solange keine universelle Fehlerkorrektur verfügbar ist.

Zusammenfassung der offenen Fragen (Future Work)

Das Paper identifiziert mehrere Bereiche für zukünftige Forschung:

1. Verschärfung der POVM-Schranke: Kann die Schranke von $O(\epsilon^{1/4})$ auf $O(\epsilon^{1/2})$ verbessert werden?
2. Rauschtoleranz: Analyse der Robustheit gegenüber realistischen Quantenrauschen (Depolarizing, Dephasing).
3. Formalisierung: Eine formale Definition von „Fehlertoleranz-freiem Quantenspeicher" und ein strenger Beweis des Lifting-Theorems für dieses spezifische Setting (derzeit nur informell).

Insgesamt stellt die Arbeit einen wichtigen Schritt dar, um die Lücke zwischen theoretischen Quanten-Kryptographie-Konzepten und praktisch umsetzbaren, sicheren One-Time-Programmen zu schließen.