A Practical Protocol for Quantum Oblivious Transfer from One-Way Functions

Dieser Beitrag stellt ein neues, praktisches und simulations-sicheres Quanten-Protokoll für die oblivious Transfer vor, das auf Einwegfunktionen im Plain-Modell basiert, die Effizienz für die experimentelle Realisierung verbessert und gleichzeitig die Fehlerkorrektur durch äquivoke und relaxiert extrahierbare Quanten-Bit-Commitments adressiert.

Das Wesentliche

Stellen Sie sich vor, Sie befinden sich auf einer Zaubershow, bei der zwei Personen, Alice und Bob, ein Spiel namens „Geheime Wahl" spielen möchten.

Das Spiel: Oblivious Transfer

In diesem Spiel verfügt Alice über zwei geheime Nachrichten (nennen wir sie Nachricht A und Nachricht B). Bob möchte eine davon auswählen, um sie zu sehen.

• Der Haken: Bob darf die andere Nachricht nicht einsehen können.
• Der Haken 2: Alice darf nicht wissen, welche Bob ausgewählt hat.

Dies wird als Oblivious Transfer (OT) bezeichnet. Es ist ein fundamentaler Baustein für sicheres Rechnen, vergleichbar mit einer digitalen „Blindbox", bei der der Verkäufer nicht weiß, welche Box Sie geöffnet haben, und Sie die andere Box nicht öffnen können.

Das Problem: Die alten Protokolle waren zu fragil

Lange Zeit wussten Wissenschaftler, wie man dies mithilfe der Quantenmechanik (unter Verwendung winziger Lichtteilchen, sogenannter Photonen) realisieren kann. Die alten Methoden wiesen jedoch drei gravierende Mängel auf, die einen Aufbau in einem echten Labor unmöglich machten:

1. Zu empfindlich: Wenn ein Photon verloren ging oder seinen Zustand aufgrund eines winzigen Rauschens (wie einer Erschütterung des Tisches) änderte, musste das gesamte Spiel neu gestartet werden. Es war, als würde man versuchen, ein Kartenhaus in einem Hurrikan zu bauen.
2. Zu schwerfällig: Die alten Methoden erforderten eine astronomische Anzahl von Photonen – etwa 10 Billionen (10¹³) für eine einzige Runde. Selbst mit den schnellsten Lasern würde dies Monate dauern, um sie zu senden.
3. Zu kompliziert: Sie stützten sich auf komplexe mathematische Beweise, die mit Standard-Technologie, die im Handel erhältlich ist, schwer zu implementieren waren.

Die Lösung: Ein praktisches, „rauschtolerantes" Protokoll

Die Autoren dieses Papers haben eine neue Version dieses Spiels entwickelt, die praktisch, schnell und robust ist. Hier ist, wie sie es erreicht haben, unter Verwendung einiger einfacher Analogien:

1. Das „Fehlerkorrigierende Netz" (Umgang mit Rauschen)

Im alten Spiel war das gesamte Deck ruiniert, wenn Sie eine Karte fallen ließen. In diesem neuen Spiel verwenden Alice und Bob ein Sicherheitsnetz.

• Die Metapher: Stellen Sie sich vor, Alice sendet eine Nachricht, die auf einem Stück Papier geschrieben ist, sendet aber auch einen „Prüfwert" (einen geheimen Code, der Ihnen mitteilt, ob das Papier zerrissen wurde).
• Wie es funktioniert: Selbst wenn einige Photonen verloren gehen oder ihren Zustand ändern (Rauschen), verwendet das Protokoll Fehlerkorrekturcodes (wie ein Netz, das die heruntergefallenen Karten auffängt), um die Fehler zu beheben. Das bedeutet, dass das Spiel nicht abstürzt, nur weil das Labor nicht perfekt ist.

2. Der „Einmalpass" (Effizienz)

Die alten Protokolle waren wie ein Spiel, bei dem Sie eine Billion Mal eine Münze werfen mussten, um ein einziges „Kopf" zu erhalten.

• Die Metapher: Das neue Protokoll ist wie ein Hochgeschwindigkeitszug anstelle eines langsamen, verschlungenen Pfades.
• Das Ergebnis: Anstatt 10 Billionen Photonen zu benötigen, benötigen sie nur etwa 10 bis 30 Millionen. Dies reduziert die benötigte Zeit von Monaten auf nur Sekunden. Es ist der Unterschied zwischen dem Warten auf einen Brief, der mit dem Schiff ankommt, und dem Senden einer E-Mail.

3. Der „Magische Verschlusskasten" (Der technische Trick)

Um das Spiel sicher zu machen, verwenden sie eine spezielle Art von Quantenverschlusskasten (genannt „Bit Commitment").

• Der alte Weg: Der Verschlusskasten war so streng, dass bei jedem Versuch des Betrugs das gesamte System zusammenbrach.
• Der neue Weg: Die Autoren erfanden einen „entspannten" Verschlusskasten.
  • Stellen Sie sich einen Verschlusskasten vor, der normalerweise ein einziges, unveränderliches Geheimnis enthält.
  • Die neue Version sagt: „Wir brauchen nicht jeden einzelnen Verschlusskasten perfekt. Wir brauchen nur, dass die meisten von ihnen fest verschlossen sind."
  • Diese „entspannte" Regel ermöglicht es ihnen, die schweren, wiederholenden Schritte der alten Protokolle zu überspringen, was enorme Mengen an Zeit und Ressourcen spart, während das Spiel dennoch sicher bleibt.

Das große Ganze

Die Autoren haben nicht nur bewiesen, dass dies auf dem Papier funktioniert; sie lieferten einen Bauplan für den Bau.

• Sie zeigten, dass mit aktueller Technologie (derselben Art, die in der Quantenschlüsselverteilung verwendet wird, die bereits in Städten getestet wird), dieses Spiel heute gespielt werden kann.
• Sie berechneten genau, wie viele Photonen benötigt werden und wie lange es dauert, und bewiesen, dass ein sicheres, quantenmechanisches Netzwerk mit mehreren Parteien kein ferner Traum mehr ist, sondern ein machbares Ingenieursprojekt.

Kurz gesagt: Sie haben ein fragiles, langsames und theoretisches Quantenspiel in ein stabiles, schnelles und praktisches Werkzeug verwandelt, das tatsächlich in einem Labor gebaut werden kann.

Technische Zusammenfassung

Technische Zusammenfassung: Ein praktisches Protokoll für Quanten-Oblivious-Transfer aus Einwegfunktionen

1. Problemstellung

Quanten-Oblivious-Transfer (QOT) ist eine fundamentale Primitive zur Konstruktion von Multi-Party-Computation (MPC) im Quantenkontext. Während frühere Arbeiten [6, 7] zeigten, dass QOT aus Einwegfunktionen (OWFs) und Quantenressourcen aufgebaut werden kann, stießen diese Protokolle auf erhebliche Hindernisse für die experimentelle Realisierung. Die identifizierten Hauptprobleme waren:

• Empfindlichkeit: Bestehende Protokolle waren nicht tolerant gegenüber experimentellen Fehlern (z. B. Bit-Flipps während der Zustandsverteilung).
• Implementierungskomplexität: Die Abhängigkeit von Zero-Knowledge-Beweisen, die keine Black-Box-Nutzung von OWFs ermöglichten, machte die Integration mit praktischen post-quanten Hash-Funktionen (wie SHA) nicht-trivial.
• Ineffizienz: Die iterative Struktur vorheriger Protokolle erforderte eine unpraktische Anzahl von Quantenzuständen (z. B. $\sim 10^{13}$ BB84-Zustände pro Durchlauf), was zu Übertragungszeiten in der Größenordnung von Monaten führte.

Die Autoren zielen darauf ab, ein rauschtolerantes, effizientes QOT-Protokoll auf Basis von OWFs im Plain-Modell bereitzustellen, das für aktuelle experimentelle Aufbauten machbar ist.

2. Methodik und technischer Ansatz

Die vorgeschlagene Lösung konstruiert ein simulations-sicheres QOT-Protokoll durch die Einführung einer neuen kryptografischen Primitive: eines Equivocal und Relaxed-Extractable (ERE) Bit Commitment-Schemas.

Kerninnovationen:

• Relaxed Extractability: Die Autoren stellen fest, dass vollständige Extractability nicht strikt notwendig ist, um die Sicherheit von QOT zu beweisen. Sie führen „relaxed extractability" ein, bei der ein Simulator die kommittierte Nachricht für einen großen Anteil der Commitments extrahieren kann, während ein vernachlässigbarer Anteil unextrahierbar bleiben darf. Diese Lockerung ermöglicht eine effizientere Protokollstruktur.
• Rauschtoleranz durch Fehlerkorrektur: Im Gegensatz zu früheren Arbeiten, die rauschfreie Geräte voraussetzten, integriert dieses Protokoll lineare fehlerkorrigierende Codes (speziell syndrombasierte Codes wie LDPC). Der Sender sendet Syndrome kodierter Werte, was dem Empfänger (oder einem Simulator) ermöglicht, Fehler zu korrigieren und korrekte Seeds auch bei Vorhandensein von Rauschen zu extrahieren.
• Effiziente Seed-Destillation: Das Protokoll nutzt Privatsphärenverstärkungstechniken (Leftover Hash Lemma) auf BB84-Zuständen, um zufällige Seeds zu destillieren. Diese Seeds dienen als Schlüssel für equivocal Commitments. Die Struktur gruppiert diese Seeds in Familien, um parallele Commitments zu ermöglichen und den quadratischen Overhead zu vermeiden, der in früheren Compilern zu finden war.
• Commitment-Struktur: Das ERE-Commitment-Schema kombiniert:
  1. EqCommitment: Ein Compiler, der ein standardmäßiges statistisch bindendes Commitment in ein equivocal Commitment verwandelt. Die Autoren modifizieren den ursprünglichen Compiler [7], indem sie die Anzahl der sequenziellen Wiederholungen von $\lambda$ auf eine einzelne Instanz reduzieren und dabei vollständige Bindung gegen „relaxed binding" tauschen.
  2. ERE-Commitment: Ein höherstufiges Protokoll, das das EqCommitment-Schema verwendet. Es umfasst, dass der Sender BB84-Zustände sendet, der Empfänger Messergebnisse commitet, und eine Herausforderungsphase, in der eine Teilmenge zur Verifizierung geöffnet wird. Die verbleibenden Zustände werden verwendet, um Seeds für die Verschlüsselung der finalen Nachricht zu generieren.

Protokollablauf (Protokoll 1):

1. Quantenübertragung: Alice sendet $2\lambda_{OT}$ BB84-Zustände an Bob.
2. Commitment: Bob misst und commitet seine Basiswahlen und Ergebnisse unter Verwendung des ERE-Commitment-Schemas.
3. Herausforderung: Alice fordert eine zufällige Teilmenge $T$ der Commitments heraus. Bob öffnet diese, um die Konsistenz mit Alices gesendeten Zuständen zu verifizieren (unter Berücksichtigung des experimentellen Fehlers $\alpha$).
4. Schlüsselgenerierung: Alice sendet die Basisinformationen für die nicht herausgeforderte Menge $\bar{T}$. Bob partitioniert $\bar{T}$ in Mengen $I_0$ und $I_1$ basierend auf übereinstimmenden Basen.
5. Verschlüsselung: Alice sendet Fehlerkorrektursyndrome und verschlüsselt ihre Nachrichten $m_0, m_1$ unter Verwendung von Seeds, die aus den nicht herausgeforderten Zuständen und einem Pseudorandom Generator (PRG) abgeleitet sind.
6. Entschlüsselung: Bob korrigiert seine Fehler unter Verwendung der Syndrome und entschlüsselt die Nachricht, die seinem Wahlbit $b$ entspricht.

3. Hauptbeiträge

• Neue Primitive: Die Definition und Konstruktion eines Equivocal und Relaxed-Extractable (ERE) Bit Commitment-Schemas auf Basis von OWFs.
• Rauschtoleranter QOT: Ein QOT-Protokoll, das experimentelle Fehler (Bit-Flipps und Multi-Photonen-Ereignisse) explizit durch syndrombasierte Fehlerkorrektur behandelt, eine Eigenschaft, die in früheren theoretischen Konstruktionen fehlte.
• Effizienzverbesserung: Durch Optimierung der Commitment-Struktur und Nutzung von Fehlerkorrektur reduziert das Protokoll die erforderliche Anzahl von BB84-Zuständen von $\sim 10^{13}$ (in [7]) auf $\sim 10^7$.
• Multi-OT-Destillation: Das Protokoll ermöglicht die Destillation mehrerer OT-Schlüssel ($n_{OT}$) aus einem einzigen Durchlauf des Protokolls, was für eine effiziente MPC-Implementierung entscheidend ist.
• Analytischer Rahmen: Die Arbeit liefert analytische Ausdrücke, um die erforderlichen Quantenressourcen gegen Ziel-Sicherheitsparameter (Trace-Distanz $\Delta$) zu benchmarken, unter Berücksichtigung physikalischer Fehlerraten ($\alpha$) und Leckage ($\vartheta$).

4. Ergebnisse und Leistung

Die Autoren stellen einen Leistungsbenchmark (Tabelle 1) bereit, der ihr Protokoll mit [7] und [21] für eine Ziel-Trace-Distanz $\Delta \le 10^{-15}$ vergleicht:

• Ressourcenreduktion: Die erforderliche Anzahl von BB84-Zuständen ($N_{BB84}$) wird auf ungefähr $1,43 \times 10^6$ (ideal) bis $3,33 \times 10^7$ (realistisches Rauschsetting) reduziert, verglichen mit $2,27 \times 10^{13}$ für das Protokoll in [7].
• Zeiteffizienz: Diese Reduktion übersetzt sich in eine Erfassungszeit ($T_{acq}$) von Sekunden (z. B. 1,43 s bis 43,6 s unter Annahme einer Rate von 1 MHz), während die vorherige Arbeit [7] ungefähr 8,6 Monate erfordern würde.
• Sicherheit: Das Protokoll wird als simulations-sicher gegen böswillige Parteien im Plain-Modell bewiesen und stützt sich ausschließlich auf die Existenz von post-quanten Einwegfunktionen.

5. Bedeutung und Behauptungen

Die Arbeit behauptet, dass sie die Lücke zwischen theoretischer Quantenkryptografie und praktischer Implementierung schließt. Durch die Beseitigung der Anforderung nach rauschfreien Geräten und die drastische Reduktion des Quantenressourcen-Overheads behaupten die Autoren, dass ihr Protokoll die experimentelle Realisierung von QOT (und damit von Quanten-MPC) mit aktueller Technologie machbar macht.

Die Autoren betonen, dass ihre Konstruktion vergleichbare BB84-Kosten wie auf Random-Oracle-Modell (ROM) basierende Protokolle [21] erreicht, aber unter streng schwächeren rechnerischen Annahmen operiert (Plain-Modell mit OWFs statt ROM). Sie geben ausdrücklich an, dass ihr Ziel eine „praktische Implementierung" ist, und sie beanspruchen nicht, die klassische Effizienz von ROM-basierten Commitments zu erreichen, sondern vielmehr einen gangbaren Weg für quantensicheren OT in der realen Welt zu bieten. Die Arbeit hebt zudem hervor, dass die Eigenschaft der relaxed extractability für die Sicherheit ausreichend ist, eine technische Erkenntnis, die Effizienzgewinne ermöglicht, ohne die simulationsbasierten Sicherheitsgarantien zu beeinträchtigen, die für MPC erforderlich sind.