New Quantum Internet Applications via Verifiable One-Time Programs

Die Autoren stellen verifizierbare Einmalprogramme vor, die unter Verwendung von Ein-Qubit-Zuständen und klassischen kryptografischen Primitive eine neue, einstufige sichere Berechnung ermöglichen und damit Anwendungen wie Auktionen, Konsensprotokolle und differenziell private Aggregation mit nur minimalen Quantenanforderungen unterstützen.

Das Wesentliche

Stellen Sie sich vor, Sie möchten ein geheimes Rezept an einen Koch senden, damit dieser ein Gericht für Sie zubereitet. Aber Sie haben zwei große Sorgen:

1. Der Koch könnte das Rezept kopieren und an alle weitergeben.
2. Der Koch könnte das Rezept verfälschen, um Ihnen ein schlechtes Gericht zu servieren, und Sie würden es erst merken, wenn es zu spät ist.

In der klassischen Welt der Kryptografie ist das fast unmöglich zu lösen, ohne dass man sich blind auf jemanden verlässt. Dieser Artikel von Lev Stambler schlägt nun einen Weg vor, wie wir das mit Hilfe von Quantentechnologie (aber nur mit sehr einfachen, fast schon „kindlichen" Quanten-Tools) lösen können.

Hier ist die Erklärung der Kernideen in einfachen Worten:

1. Das Problem: Das „Einmal-Programm" (One-Time Program)

Stellen Sie sich ein Einmal-Programm wie einen zerbrechlichen Glasbrief vor. Darin steht ein geheimes Rezept. Wenn der Empfänger den Brief öffnet, um das Rezept zu lesen, zerfällt der Glasbrief sofort in tausende Scherben. Das Rezept kann also nur ein einziges Mal gelesen werden. Danach ist es weg.

Das ist toll für den Datenschutz, aber es hat einen Haken: Was, wenn der Absender einen gefälschten Glasbrief schickt? Der Empfänger öffnet ihn, sieht nur Unsinn, und hat keine Ahnung, ob das Original echt war oder nicht. Er kann das Programm nicht verifizieren (überprüfen), bevor er es benutzt.

2. Die Lösung: Verifizierbare Einmal-Programme (Ver-OTPs)

Der Autor erfindet nun „Verifizierbare Einmal-Programme".
Stellen Sie sich vor, statt eines einzelnen Glasbriefes schickt der Absender 100 kleine Glasampullen.

• In jeder Ampulle ist ein winziger Teil des Geheimnisses (ein „Fragment").
• Der Absender sagt: „Wenn du 51 dieser Ampullen öffnest, kannst du das ganze Geheimnis wieder zusammensetzen."
• Der Trick: Der Empfänger darf zuerst zufällig 10 Ampullen öffnen, um zu prüfen, ob sie echt sind und ob sie zusammenpassen.
• Wenn diese 10 Ampullen in Ordnung sind, ist die Wahrscheinlichkeit extrem hoch, dass auch die restlichen 90 Ampullen echt sind.
• Der Empfänger öffnet dann die restlichen Ampullen, setzt das Geheimnis zusammen, nutzt es einmal, und dann ist alles weg.

Die Quanten-Technologie: Um diese Ampullen zu bauen, braucht man keine riesigen, komplizierten Quantencomputer. Es reicht, einfache Lichtteilchen (Qubits) zu schicken, ähnlich wie bei der bekannten „BB84"-Methode, die heute schon über hunderte Kilometer funktioniert. Das macht die Idee mit heutiger Technik machbar.

3. Der große Durchbruch: „Offene Sichere Berechnung" (OSC)

Jetzt kommt das eigentliche Genie: Wie nutzt man diese Ampullen, um komplexe Dinge zu tun? Der Autor stellt ein neues System vor, das er „Offene Sichere Berechnung" nennt.

Die Analogie: Die geheime Auktion ohne Anmeldung
Stellen Sie sich eine Auktion vor, bei der niemand vorher anmelden muss.

• Das Szenario: Tausende Leute wollen ein Gebot abgeben. Niemand weiß, wer dabei ist.
• Das Problem: Normalerweise müsste sich jeder vorher registrieren, damit die Auktion weiß, wer mitmachen darf.
• Die neue Lösung (OSC): Jeder schickt einfach sein Gebot in einem dieser „verifizierbaren Glasbriefe" an den Auktionator.
• Der Auktionator prüft die Briefe (wie oben beschrieben). Wenn sie echt sind, rechnet er aus, wer gewonnen hat.
• Das Besondere: Der Auktionator kann nicht betrügen. Er kann nicht sagen: „Ich ignoriere Gebot A und nehme nur Gebot B", weil die Verifizierung sicherstellt, dass er alle echten Gebote in die Berechnung einbeziehen muss, um das Ergebnis zu erhalten.

4. Was kann man damit machen? (Anwendungen)

Der Artikel zeigt drei coole Beispiele, wie diese Technik die Welt verändern könnte:

• Einmal-Auktionen (Sealed-Bid Auctions):
  Stellen Sie sich vor, Sie wollen ein Haus kaufen. Sie werfen Ihr Gebot in einen unsichtbaren Briefkasten. Der Verkäufer öffnet alle Briefe auf einmal, findet das höchste Gebot, und niemand weiß, was die anderen geboten haben. Und das alles in einem einzigen Schritt (kein Hin und Her von Nachrichten).

• Stimmabgabe für Konsens (Atomic Proposals):
  In großen Computer-Netzwerken (wie Blockchain) müssen viele Computer sich auf eine Entscheidung einigen. Normalerweise dauert das lange. Mit OSC kann ein „Führer" eine Idee vorschlagen, und alle anderen stimmen in einem einzigen Schritt zu. Wenn die Mehrheit zustimmt, wird die Entscheidung sofort festgeschrieben. Das macht das Internet viel schneller.

• Geheime Statistik (Differenzielle Privatsphäre):
  Stellen Sie sich vor, eine Firma will wissen, wie viele Menschen in einer Stadt krank sind, ohne dass jemand seinen Namen verrät.

  • Jeder Bürger schickt eine verschlüsselte Zahl (z. B. „Ich bin krank" oder „Ich bin gesund") plus ein bisschen zufälliges „Rauschen" (Störgeräusch) dazu.
  • Der Rechner summiert alles. Durch das Rauschen kann niemand herausfinden, wer genau krank war, aber die Gesamtzahl ist trotzdem fast genau.
  • Der Clou: Niemand muss sich vorher registrieren. Jeder kann einfach so mitmachen.

Zusammenfassung

Dieser Artikel sagt im Grunde: „Wir müssen nicht warten, bis riesige, fehleranfällige Quantencomputer erfunden sind, um Quanten-Sicherheit zu nutzen."

Stattdessen nutzen wir einfache Quanten-Tools (wie einzelne Lichtteilchen), kombiniert mit cleverer Mathematik (Verschlüsselung), um ein System zu bauen, bei dem:

1. Programme nur einmal laufen.
2. Man prüfen kann, ob sie echt sind.
3. Man niemanden vorher kennen muss, um sicher mitzumachen.

Es ist wie ein magischer Briefkasten, der sich selbst zerstört, nachdem er gelesen wurde, aber vorher garantiert, dass er nicht leer oder manipuliert war. Das könnte die Art und Weise, wie wir Auktionen, Wahlen und Datenschutz im Internet betreiben, revolutionieren.

Technische Zusammenfassung

1. Problemstellung und Motivation

Das Quanteninternet verspricht revolutionäre Anwendungen jenseits von Quantenschlüsselverteilung (QKD) und Positionsverifikation. Die meisten bestehenden Vorschläge erfordern jedoch hochkomplexe Quantenressourcen (wie verschränkte Zustände oder Quantenspeicher mit langer Kohärenzzeit), die weit über die derzeit verfügbare Technologie hinausgehen.

Ein vielversprechender Ansatz nutzt einfache BB84-ähnliche Quantenzustände (Einzel-Qubit-Zustände), die bereits über große Distanzen (z. B. 650 m Glasfaser) übertragen werden können. Ein bekanntes primitives auf dieser Basis sind One-Time Programs (OTPs), die eine Funktion nur einmal ausführen lassen. Allerdings sind OTPs, die auf Einzel-Qubit-Zuständen basieren, inhärent ephemer (kurzlebig), da die Kohärenzzeit der Qubits begrenzt ist. Dies führt zu sogenannten ephemeral OTPs (eOTPs).

Das Hauptproblem besteht darin, dass die Kurzlebigkeit dieser eOTPs ihre Nutzbarkeit einschränkt: Ein Empfänger muss sofort online sein, was den Zweck eines „Programms", das zu einem späteren Zeitpunkt ausgeführt werden soll, untergräbt. Zudem fehlt es an Mechanismen, um vor der Ausführung zu verifizieren, ob das Programm korrekt und vertrauenswürdig ist, ohne dabei geheime Informationen preiszugeben.

2. Methodik und Kernkonzepte

Die Arbeit stellt zwei neue primitive vor, die diese Lücken schließen und eine neue Architektur für quantenunterstützte Kryptographie ermöglichen:

A. Verifiable One-Time Programs (Ver-OTPs)

Ver-OTPs erweitern die klassische OTP-Idee um eine Verifizierungsfunktion.

• Funktionsweise: Der Empfänger kann vor der Ausführung überprüfen, ob das OTP korrekt bezüglich einer öffentlich bekannten Relation $\mathcal{R}$ zu den Eingabedaten aufgebaut ist. Diese Verifizierung ist nicht-interaktiv und enthüllt nichts über die geheimen Programm-Daten außer deren Gültigkeit.
• Konstruktion:
  • Garbled Circuits: Die Funktion wird als verschlüsselte Schaltung (Garbled Circuit) bereitgestellt.
  • Verifiable One-Time Memories (Ver-OTMs): Anstelle von einfachen OTMs wird ein Cut-and-Choose-Verfahren in Kombination mit Secret Sharing verwendet. Für jede Geheimnis-Drähte (Wire Labels) werden $\zeta$ Geheimnis-Anteile (Shares) generiert. Diese werden in verschiedene einzelne-Bit-OTPs gepackt.
  • Verifizierung: Der Empfänger wählt zufällig einen kleinen Teil dieser OTPs aus, um sie zu „öffnen" und die Gültigkeit der Shares sowie zugehörige Zero-Knowledge-Beweise zu prüfen. Wenn diese bestehen, wird mit überwältigender Wahrscheinlichkeit garantiert, dass die restlichen, nicht geprüften OTPs korrekt sind.
  • Sicherheit: Die Schwelle für das Secret Sharing ($\zeta/2 + 1$) stellt sicher, dass ein böswilliger Empfänger nicht beide möglichen Eingabe-Labels ($\kappa_0$ und $\kappa_1$) rekonstruieren kann.
  • Annahmen: Die Konstruktion nutzt nicht-interaktive Zero-Knowledge-Beweise (NIZKs), Commitments und eine Common Reference String (CRS) mit einer Falltür (Trapdoor) für die Simulation.

B. Open Secure Computation (OSC)

Aufbauend auf Ver-OTPs wird das neue Paradigma der Open Secure Computation (OSC) eingeführt.

• Definition: Ein Single-Round-Protokoll für sichere Berechnungen, das keine Vorregistrierung der Sender benötigt. Eine unbekannte Menge an Sendern kann Eingaben an einen bekannten (aber nicht vertrauenswürdigen) Empfänger senden, der eine Funktion auf diesen Eingaben berechnet.
• Mechanismus:
  • Multi-Key Homomorphic Encryption (MHE): Jeder Sender erzeugt ein Schlüsselpaar und verschlüsselt seine Eingabe.
  • Ver-OTP als Entschlüsselungs-Proxy: Jeder Sender erstellt ein Ver-OTP, das seine geheime Entschlüsselungs-Funktion kodiert. Dieses OTP wird nur dann eine teilweise Entschlüsselung ausgeben, wenn die verschlüsselte Eingabe des Senders korrekt ist.
  • Adaptive Partitionierung: Der Empfänger kann die erhaltenen Eingaben in disjunkte Gruppen aufteilen und die Funktion $f$ auf jede Gruppe separat anwenden. Dies erfordert eine modifizierte Sicherheitsdefinition für MHE, die Teilmengen von Schlüsseln und Ciphertexts sowie Simulationen ohne Kenntnis des Ergebnisses erlaubt.
• Quantenbedarf: Minimal. Es werden nur Einzel-Qubit-Zustände für die OTPs benötigt. Der Rest der Komplexität (MHE, NIZK, Garbled Circuits) ist rein klassisch.

3. Hauptbeiträge

1. Einführung von Ver-OTPs: Ein neues primitives, das die Verifizierbarkeit von ephemeren Quanten-OTPs ermöglicht, ohne die Geheimhaltung der Eingaben zu gefährden.
2. Entwicklung von OSC: Ein Single-Round-Modell für sichere Berechnungen ohne Vorregistrierung, das die Flexibilität von „offenen" Systemen mit der Sicherheit von Quanten-OTPs verbindet.
3. Anwendungsprotokolle: Demonstration, wie OSC folgende Szenarien in einem einzigen Kommunikationsrunden realisiert:
   • Versiegelte Gebotsauktionen (Sealed-Bid Auctions): Einmalige Auktionen, bei denen der Auktionator nur eine Runde ausführen kann und eine Mehrzahl der registrierten Bieter einbeziehen muss.
   • Atomare Vorschläge (Atomic Proposes): Ein Baustein für Konsensprotokolle (wie PBFT oder Ethereum), bei dem ein Führer einen Wert vorschlägt und eine Mehrheit der Parteien attestiert.
   • Differenziell private statistische Aggregation: Aggregation von Daten unbekannter Parteien ohne Vorregistrierung, unter Einhaltung des Datenschutzes.
   • Fair Exchange: Ein Protokoll für den fairen Austausch digitaler Güter, unterstützt durch Blockchain und Ver-OTPs.

4. Ergebnisse und technische Details

• Effizienz und Machbarkeit: Der Quantenanteil ist auf das absolute Minimum beschränkt (Einzel-Qubit-Zustände), was die Implementierung mit nahe-zukünftiger Quantentechnologie (Near-Term Quantum Technology) ermöglicht. Die klassische Komplexität wird durch moderne Kryptographie-Primitiven (MHE, NIZK) bewältigt.
• Sicherheit: Die Protokolle basieren auf einer simulationsbasierten Sicherheitsdefinition (Simulation-Soundness).
  • Gegen einen böswilligen Sender wird sichergestellt, dass das OTP korrekt ist.
  • Gegen einen böswilligen Empfänger wird sichergestellt, dass er keine Informationen über die Eingaben der anderen Sender erhält, die über das Ergebnis der Funktion hinausgehen.
• Herausforderungen:
  • Die Konstruktion erfordert eine Common Reference String (CRS) Annahme, deren Entfernung ein offenes Problem bleibt.
  • Die verwendete MHE-Sicherheit muss gegenüber existierenden Definitionen erweitert werden (z. B. Unterstützung für Teilmengen von Schlüsseln und Simulation ohne Funktionsausgabe). Der Autor argumentiert, dass dies mit bestehenden Schemata möglich ist, liefert aber keine vollständige Konstruktion.
  • Die aktuelle Konstruktion ist nicht UC-sicher (Universal Composability), da sie Rewinding für die Simulation benötigt.

5. Bedeutung und Ausblick

Diese Arbeit bietet einen neuen Rahmen für quantenunterstützte Kryptographie, der die Kluft zwischen theoretischen Quantenversprechen und praktischer, naher Zukunftstechnologie schließt.

• Praktische Relevanz: Da die benötigten Quantenressourcen (Einzel-Qubits) bereits über große Distanzen übertragbar sind, sind die vorgeschlagenen Anwendungen (wie Auktionen oder Konsensmechanismen) potenziell in naher Zukunft realisierbar.
• Paradigmenwechsel: OSC ermöglicht es, vertrauenswürdige Berechnungen in Umgebungen durchzuführen, in denen keine zentrale Registrierung oder Vorab-Kommunikation möglich ist („Open" Nature).
• Offene Fragen: Die Autoren identifizieren mehrere Forschungsrichtungen, darunter die Entfernung der CRS-Annahme, die Verbesserung der Effizienz, die Hinzufügung von Fehlertoleranz für reale, verrauschte Quantensysteme und die Erweiterung auf vollquantenmechanische Eingaben und Funktionen.

Zusammenfassend demonstriert das Papier, dass selbst die einfachsten Quantenzustände, kombiniert mit cleverer klassischer Kryptographie, mächtige neue kryptographische Primitive und Anwendungen ermöglichen können, die bisher als unmöglich oder zu ressourcenintensiv galten.