Technisches Resümee: Beliebig verlusttolerante Quanten-Positionsverifizierung in einer einzelnen Ausführung

1. Problemstellung

Die Quanten-Positionsverifizierung (Quantum Position Verification, QPV) zielt darauf ab, den räumlichen Standort eines unvertrauenswürdigen Provers unter Verwendung von relativistischen Signalisierungsbeschränkungen und Quanteninformationen zu zertifizieren. Während das No-Cloning-Theorem klassische Kopierangriffe verhindert, ist eine bedingungslose Sicherheit gegen Angreifer, die beliebig große Verschränkung teilen, unmöglich. Folglich konzentriert sich die Forschung auf das Modell der begrenzten Verschränkung (bounded-entanglement, BE), bei dem Angreifer eine begrenzte Anzahl an verschränkten Qubits teilen.

Ein kritisches praktisches Hindernis für QPV ist der Photonenverlust. In Glasfaserkabeln steigt der Übertragungsverlust exponentiell mit der Distanz an. Standardmäßige QPV-Protokolle (z. B. $QPV_{BB84}$, $QPV^f_{BB84}$ und das parallele $QPV^{f:n\to m}_{BB84}$) setzen eine ideale Übertragung voraus. Diese Annahme schafft eine fundamentale Schwachstelle: Ein Angreifer kann Qubits abfangen, sie in zufälligen Basen messen und Ergebnisse nur dann melden, wenn die Basisvermutung korrekt war, andernfalls „Verlust“ deklarieren. Diese Strategie bricht die Sicherheit, sobald die Übertragungsrate unter 50 % fällt.

Vorherige Arbeiten adressierten Verlust und Verschränkung entweder separat oder gleichzeitig, jedoch nur in sequenziellen Settings. Speziell führte [ABB+23] eine auf Commitment basierende Modifikation ($c-QPV^f_{BB84}$) ein, die beliebigen Verlust toleriert, indem sie vom Prover verlangt, die empfangenen Qubits zu committen, bevor er die Messbasis erfährt. Diese Technik stützte sich jedoch auf die sequenzielle Struktur des Protokolls, bei der wiederholte Runden es den Verifizierern ermöglichen, inkonsistente Commitments zu erkennen. Diese Techniken lassen sich nicht auf Single-Execution (parallele) Protokolle übertragen, welche für die praktische Implementierung und als Subroutinen in größeren kryptographischen Schemata bevorzugt werden. Bestehende Single-Execution-Protokolle sind entweder nicht verlusttolerant oder erfordern Quantenkommunikation mit Lichtgeschwindigkeit, was ihre Anwendbarkeit einschränkt.

2. Methodik

Die Autoren schlagen eine Commitment-basierte Modifikation des parallelen Single-Execution-Protokolls $QPV^{f:n\to m}_{BB84}$ vor, bezeichnet als $c-QPV^{f:n\to m}_{BB84}$.

Protokollstruktur

Das Protokoll umfasst zwei Verifizierer ($V_0, V_1$) und einen Prover ($P$):

1. Vorbereitung: Die Verifizierer generieren klassische Inputs $x, y \in \{0,1\}^n$ und Quantenzustände (BB84-Qubits) basierend auf einer Funktion $z = f(x,y)$.
2. Distribution: Quantenzustände werden an $P$ gesendet, gefolgt von klassischen Strings $x$ und $y$, die zeitlich so abgestimmt sind, dass sie gleichzeitig am behaupteten Ort eintreffen.
3. Commitment (neuer Schritt): Nach Erhalt der Quantensysteme, aber bevor er $x$ und $y$ erfährt, broadcastet der Prover einen Commitment-String $c \in \{0,1\}^m$, der angibt, welche Qubits erfolgreich empfangen wurden ($c_i=1$) und welche verloren gingen ($c_i=0$).
4. Verifizierungsbedingung: Das Protokoll wird nur fortgesetzt, wenn die Anzahl der committeten Qubits $|c| \geq k$, wobei $k$ ein vordefinierter Schwellenwert ist.
5. Messung: Sobald $x$ und $y$ eintreffen, berechnet $P$ $z = f(x,y)$ und misst nur die Qubits in der Menge der committeten Indizes $C = \{i \mid c_i=1\}$ in den durch $z_C$ spezifizierten Basen.
6. Verifizierung: Die Verifizierer akzeptieren, wenn die gemeldeten Ergebnisse innerhalb einer Fehlermarge $\gamma$ für die Teilmenge $C$ mit den erwarteten Werten übereinstimmen.

Techniken der Sicherheitsanalyse

Die Sicherheitsanalyse adressiert die Herausforderung, dass im Gegensatz zur sequenziellen Wiederholung eine einzelne Ausführung nur einen Commitment-String liefert, was die Erkennung von Inkonsistenzen über Runden hinweg verhindert. Die Autoren nutzen folgende Techniken:

• No-Signalling-Beschränkungen: Die Analyse nutzt die Tatsache, dass Angreifer (Alice und Bob) räumlich getrennt sind. Ihre gemeinsame Commitment-Verteilung muss No-Signalling-Bedingungen erfüllen; insbesondere kann Alices Commitment nicht von Bobs Input $y$ abhängen und umgekehrt.
• Zerlegung der Akzeptanzwahrscheinlichkeit: Die Autoren zerlegen die gesamte Akzeptanzwahrscheinlichkeit in eine Summe über mögliche Commitment-Strings $c$. Sie begrenzen die bedingte Akzeptanzwahrscheinlichkeit $Pr[\text{accept } w_C \mid c]$ für ein festes $c$, indem sie diese mit der Sicherheit des ursprünglichen $QPV^{f:n\to m}_{BB84}$-Protokolls, beschränkt auf die Teilmenge $C$, in Beziehung setzen.
• Exponentieller Zerfall: Durch die Kombination der No-Signalling-Beschränkungen mit dem exponentiellen Zerfall der Soundness des ursprünglichen Protokolls (gesteuert durch den Parameter $\lambda_\gamma$) leiten sie eine globale Schranke ab, die exponentiell mit dem Schwellenwert $k$ abfällt.
• Verfeinerte sequentielle Analyse: Die Autoren untersuchen auch das sequentielle Protokoll aus [ABB+23] neu. Sie ersetzen die stochastische Stoppzeit (das Warten auf eine polynomielle Anzahl erfolgreicher Runden) durch eine feste Anzahl von Runden $m$ und einen festen Schwellenwert $k$. Dies ermöglicht eine direkte Schranke für die Akzeptanzwahrscheinlichkeit, ohne sich auf „Entweder-oder“-Aussagen bezüglich inkonsistenter Commitments verlassen zu müssen.

3. Kernbeiträge

1. Erstes verlusttolerantes Single-Shot QPV: Die Arbeit präsentiert $c-QPV^{f:n\to m}_{BB84}$, das erste Protokoll, das gleichzeitig erreicht:
   • Vernachlässigbare Soundness in einer einzelnen Ausführung.
   • Sicherheit gegen Angreifer, die eine lineare Menge an Verschränkung (im Verhältnis zur Größe der klassischen Inputs) teilen.
   • Keine Anforderung an Quantenkommunikation mit Lichtgeschwindigkeit.
   • Toleranz gegenüber beliebig großen Übertragungsverlusten.
2. Generalisierung des Commitment-Paradigmas: Die Arbeit überträgt die Commitment-Modifikation erfolgreich vom sequenziellen auf das parallele Setting unter Verwendung von No-Signalling-Korrelationen und überwindet damit die Abhängigkeit von der sequenziellen Struktur, die dies zuvor verhinderte.
3. Verbesserte sequentielle Parameter: Die Arbeit verfeinert die Analyse von sequenziellen Commitment-Protokollen, indem sie stochastische Stoppzeiten durch feste Parameter ersetzt. Dies liefert verbesserte quantitative Schranken, bei denen die Akzeptanzwahrscheinlichkeit des Angreifers exponentiell mit dem Schwellenwert $k$ sinkt, mit einem Korrekturterm der Größenordnung $O(k^{-1/3})$ (verbessert von $O(r^{-1/4})$ in vorangegangener Arbeit).
4. Robustheit: Das resultierende Protokoll behält die Robustheit gegenüber Rauschpegeln bis zu 3,7 % pro Qubit bei, was der Rauschtoleranz des ursprünglichen zugrunde liegenden Protokolls entspricht.

4. Ergebnisse

Das Hauptergebnis (Theorem 1.1 und Theorem 4.1) stellt fest, dass für eine geeignete Funktion $f$ die Wahrscheinlichkeit, dass ein Angreifer im BE($O(n)$)-Modell akzeptiert wird, begrenzt ist durch:
$$Pr[\text{accept } c-QPV^{f:n\to m}_{BB84}] \lesssim 2(\lambda_\gamma)^{k/2}$$
wobei $\lambda_\gamma = 2^{h(\gamma)}(\frac{1}{2} + \frac{1}{2}\sqrt{2})$ und $h(\cdot)$ die binäre Entropiefunktion ist.

• Verlusttoleranz: Die Sicherheit hängt von $k$ (der Anzahl der erfolgreich empfangenen Qubits) ab, nicht von der Gesamtzahl der übertragenen Qubits $m$. Somit bleibt das Protokoll sicher, selbst wenn die Übertragungsrate beliebig niedrig ist, sofern genügend Qubits empfangen werden, um den Schwellenwert $k$ zu erreichen.
• Rauschtoleranz: Das Protokoll bleibt sicher für Fehlerraten $\gamma < 0,037$ (3,7 %), da dies sicherstellt, dass $\lambda_\gamma < 1$.
• Parallele Repetition: Für Protokolle, die durch parallele Repetition einer einzelnen Booleschen Funktion $g$ konstruiert werden (d. h. $f = g^{\otimes m}$), reduziert sich die Sicherheit der Commitment-basierten Version auf die Sicherheit der Nicht-Commitment-Version mit $k$ Repetitionen: $Pr[\text{accept } c-QPV^{g^{\otimes m}}_{BB84}] \leq 2\sqrt{Pr[\text{accept } QPV^{g^{\otimes k}}_{BB84}]}$.

5. Bedeutung und Ansprüche

Die Autoren behaupten, dass diese Arbeit eine kritische Lücke zwischen theoretischer Sicherheit und praktischer Implementierung von QPV schließt.

• Machbarkeit über beliebige Distanzen: Durch die Machung des Protokolls beliebig verlusttolerant ermöglicht die Arbeit QPV über lange Distanzen, auf denen Photonenverlust signifikant ist – eine Voraussetzung für den realen Einsatz.
• Praktischer Nutzen: Die Single-Execution-Natur des Protokolls wird als besonders attraktiv für Near-Term-Implementierungen und für die Verwendung als Subroutine in größeren kryptographischen Konstruktionen (z. B. Quantenschlüsselaustausch, Nachrichtenauthentifizierung) hervorgehoben, wo sequenzielle Repetition oft unpraktisch ist.
• Theoretischer Fortschritt: Die Arbeit zeigt, dass commitment-basierte Sicherheit in parallelen Settings erreicht werden kann, ohne die Sicherheitsgarantien des zugrunde liegenden Protokolls gegen Angreifer mit begrenzter Verschränkung zu opfern.
• Experimentelle Relevanz: Das Paper liefert verbesserte quantitative Parameter für experimentelle Implementierungen, indem es insbesondere die Anzahl der Runden und den Akzeptanzschwellenwert festlegt, was die Unsicherheit der Ausführungsdauer eliminiert, die vorangegangenen sequenziellen Ansätzen eigen war.

Das Paper kommt zu dem Schluss, dass $c-QPV^{f:n\to m}_{BB84}$ das erste vollständig verlusttolerante Single-Shot QPV-Protokoll darstellt, das gegen verschränkte Angreifer sicher ist, und damit effektiv die Barriere der Übertragungsrate beseitigt, die QPV zuvor auf kurze Distanzen oder idealisierte Bedingungen beschränkte.