Experimental asymmetric relativistic zero-knowledge proofs with unconditional security

Dieses Paper präsentiert ein effizientes, experimentell verifiziertes asymmetrisches relativistisches Zero-Knowledge-Proof-Protokoll, das durch die Nutzung der speziellen Relativitätstheorie und Quanten-Nichtlokalität eine bedingungslose Sicherheit gegen Quantenangriffe erreicht und dadurch die unpraktikable Round-Komplexität früherer symmetrischer Ansätze überwindet.

Das Wesentliche

Das große Ganze: Beweisen, dass man ein Geheimnis kennt, ohne es zu verraten

Stellen Sie sich vor, Sie besitzen eine geheime Schatzkarte und möchten einem skeptischen Wächter beweisen, dass Sie die Karte tatsächlich haben. Sie wollen ihm die Karte nicht zeigen (weil er sie stehlen könnte), und Sie wollen ihm auch nicht verraten, wo der Schatz liegt. Sie wollen lediglich beweisen: „Ich kenne den Weg.“

In der digitalen Welt nennt man das einen Zero-Knowledge-Proof (ZKP). Es ist der Zaubertrick, der es Ihnen ermöglicht, zu beweisen, dass Sie die Person sind, die Sie zu sein behaupten, oder dass Sie genug Geld für eine Transaktion haben, ohne Ihr Passwort oder Ihren Kontostand preiszugeben.

Das Problem: Das Quanten-Monster

Seit Jahrzehnten beruhten diese digitalen Zaubertricks auf mathematischen Rätseln, die für Menschen schwer zu lösen, aber für Computer einfach zu lösen waren. Doch Wissenschaftler bauen nun Quantencomputer, die wie superschnelle Monster sind. Diese Monster können jene alten mathematischen Rätsel fast augenblicklich lösen und damit die Sicherheit unserer heutigen digitalen Schlösser knacken.

Wir brauchen eine neue Art von Schloss, das nicht auf mathematischen Rätseln basiert, sondern auf den Gesetzen der Physik.

Die Lösung: Das „Lichtgeschwindigkeits“-Schloss

Dieses Paper stellt eine neue Art des Beweises vor, die als relativistischer Zero-Knowledge-Proof bezeichnet wird. Anstatt sich auf schwierige Mathematik zu verlassen, stützt er sich auf die Lichtgeschwindigkeit.

Die Analogie: Der zweiköpfige Drache
Stellen Sie sich vor, Sie haben einen Drachen mit zwei Köpfen (nennen wir sie Kopf A und Kopf B). Sie möchten einem Richter beweisen, dass der Drache echt ist, aber Sie dürfen nicht zulassen, dass die Köpfe miteinander kommunizieren.

• Der Richter steht weit entfernt von Kopf A.
• Ein weiterer Richter steht weit entfernt von Kopf B.
• Der Abstand ist so groß, dass selbst ein Lichtstrahl (das Schnellste im Universum) nicht in der Zeit von Kopf A zu Kopf B reisen kann, die benötigt wird, um eine Frage zu beantworten.

Da Kopf A und Kopf B nicht schnell genug kommunizieren können, um eine Lüge abzustimmen, sind sie gezwungen, die Wahrheit zu sagen. Wenn sie versuchen zu betrügen, werden sie von den Gesetzen der Physik (speziell der Tatsache, dass nichts schneller als das Licht reist) erwischt.

Was dieses Team geleistet hat

Die Forscher haben eine funktionierende Version dieses „Lichtgeschwindigkeits“-Beweises gebaut. Hier ist, wie sie ihn verbessert haben:

1. Der alte Weg war zu langsam: Frühere Versuche dieses „Zwei-Köpfe-Drachen“-Bweises waren wie der Versuch, ein riesiges Labyrinth zu lösen, indem man jeden einzelnen Pfad nacheinander durchläuft. Wenn die Karte (der Graph) groß war, hätte es tausende von Jahren gedauert, um den Beweis abzuschließen. Es war theoretisch möglich, aber praktisch unbrauchbar.
2. Der neue Weg ist schnell: Das Team hat eine intelligentere, asymmetrische Version entwickelt. Denken Sie daran wie bei einem Drachen, bei dem ein Kopf die ganze schwere Arbeit erledigt, während der andere Kopf nur Wache hält.
   • Das Ergebnis: Sie reduzierten die benötigte Zeit von „tausenden von Jahren“ auf 0,22 Sekunden.
   • Der Preis: Sie verwendeten etwas mehr „Zufälligkeit“ (wie beim mehrmaligen Mischen eines Kartendecks), aber die gesamte Datenmenge war immer noch klein genug, um auf eine moderne Festplatte zu passen (etwa 430 MB).

Das Experiment

Um zu beweisen, dass dies in der realen Welt funktioniert, bauten sie ein Experiment an der Nanjing Universität auf:

• Sie platzierten zwei Computer (die „Köpfe“) in verschiedenen Gebäuden, 300 Meter voneinander entfernt.
• Sie verwendeten Hochgeschwindigkeitslaser und GPS-Uhren, um sicherzustellen, dass die Computer nicht schneller als das Licht miteinander kommunizieren konnten.
• Sie forderten die Computer auf, zu beweisen, dass sie wissen, wie man eine komplexe Karte mit nur drei Farben färbt (ein klassisches mathematisches Rätsel), ohne die Farben zu zeigen.
• Das Ergebnis: Die Computer schlossen den gesamten Beweis in 0,22 Sekunden ab.

Warum das wichtig ist

Das Paper behauptet, dass dies ein bedeutender Schritt nach vorn ist, weil:

• Es quantensicher ist: Selbst wenn ein Quantencomputer versucht, den Code zu knacken, kann er nicht betrügen, da er die Gesetze der Physik (die Lichtgeschwindigkeit) nicht brechen kann.
• Es praktisch ist: Im Gegensatz zu früheren Versionen, die zu langsam für den praktischen Einsatz waren, ist diese Version schnell genug für den echten Gebrauch, wie etwa die Sicherung von Online-Banking oder Wahlen.
• Es bedingungslos ist: Es beruht nicht auf der Annahme „Wir glauben, dass diese Mathematik schwer ist“, sondern auf der Gewissheit „Wir wissen, dass das Licht eine Geschwindigkeitsbegrenzung hat“.

Zusammenfassung

Die Forscher nahmen eine theoretische Idee – die Nutzung der Lichtgeschwindigkeit, um Lügner zu stoppen – und bauten eine funktionierende Maschine, die dies in einem Bruchteil einer Sekunde erledigt. Sie lösten das Problem der langsamen Geschwindigkeit, indem sie eine Seite des Systems mehr arbeiten ließen, was den gesamten Prozess unglaublich schnell und sicher gegen zukünftige Quantencomputer machte.

Technische Zusammenfassung

Technisches Resümee: Experimentelle asymmetrische relativistische Null-Wissen-Beweise mit unbedingter Sicherheit

Problemstellung

Null-Wissen-Beweise (Zero-Knowledge Proofs, ZKPs) sind entscheidend für die Etablierung von Vertrauen und Privatsphäre in digitalen Ökonomien, wie etwa Kryptowährungen und Smart Contracts. Klassische ZKP-Protokolle stützen sich jedoch auf rechnerische Annahmen (z. B. die Existenz Einwegfunktionen), was sie anfällig für zukünftige Quantenangriffe macht. Während Quanten-ZKPs eine potenzielle Alternative bieten, stehen sie vor erheblichen Implementierungshürden, einschließlich des No-Cloning-Theorems, das das Quanten-Rewinding erschwert, sowie der Unmöglichkeit einer bedingungslos sicheren Quanten-Bit-Commitment.

Relativistische ZKPs (RZKPs) haben sich als Lösung herausgestellt, indem sie die rechnerischen Annahmen durch die Prinzipien der speziellen Relativitätstheorie (speziell das No-Signaling-Prinzip) ersetzen. Ein jüngster Durchbruch demonstrierte ein symmetrisches RZKP für das Graph-Drei-Färbungsproblem. Dieses symmetrische Protokoll leidet jedoch unter prohibitiven Ineffizienzen, wenn es um Quanten-Korrektheit (Sicherheit gegen Prover, die Quantenverschränkung teilen) geht. Um Quanten-Korrektheit zu gewährleisten, erfordert das symmetrische Protokoll eine Round-Komplexität von $O(|E|^4)$ (wobei $|E|$ die Anzahl der Kanten ist), was zu nicht erreichbaren Laufzeiten und massiven Randomness-Kosten für Graphen realistischer Größe führt.

Methodik

Die Autoren schlagen und implementieren experimentell ein asymmetrisches relativistisches GMW ZKP-Protokoll, das darauf ausgelegt ist, die Effizienzbeschränkungen früherer symmetrischer Ansätze zu überwinden und gleichzeitig eine bedingungslose Sicherheit gegen quantenkorrelierte Prover zu gewährleisten.

Protokolldesign

Das Protokoll umfasst zwei räblich getrennte Prover-Verifier-Paare ($P_1-V_1$ und $P_2-V_2$) und operiert über $m$ interaktive Runden, um zu beweisen, dass ein Graph $G(V, E)$ drei-färbbar ist, ohne die Färbung preiszugeben.

1. Vorbereitung: Die Prover $P_1$ und $P_2$ teilen eine zufällige Farbpermutation $\pi$ und einen Satz zufälliger Werte $B = \{b_k\}$.
2. Abfragephase (Query Phase): Der Verifier $V_1$ sendet zufällige Abfragen $X = \{x_k\}$ an $P_1$.
3. Commitment-Phase: $P_1$ berechnet Commitments $A = \{a_k\}$, wobei $a_k = x_k \cdot y_k - b_k$ (mit $y_k$ als der Farbe) und sendet diese an $V_1$.
4. Challenge-Phase: Der Verifier $V_2$ wählt eine zufällige Kante $C = \{i, j\}$ aus und sendet sie an $P_2$.
5. Reveal-Phase: $P_2$ offenbart die Farben $Y(C)$ und die entsprechenden Werte $B(C)$ an $V_2$.
6. Prüfphase (Check Phase): Die Verifier prüfen die relativistischen Constraints (um sicherzustellen, dass kein Signaling zwischen $P_1$ und $P_2$ stattfindet, indem sie die Zeitverzögerungen $|t_1 - t_4| < \tau$ und $|t_2 - t_3| < \tau$ verifizieren, wobei $\tau = d/c$) sowie die logische Konsistenz (Farben sind verschieden und stimmen mit den Commitments überein).

Theoretische Analyse

Die Autoren adressieren die Herausforderung der Quanten-Korrektheit. Im Gegensatz zu klassischen Protokollen, bei denen Bit-Commitment stark bindend ist, garantieren relativistische Bit-Commitments nur eine „Sum-Binding“-Eigenschaft. Die Autoren zeigen, dass die Wahrscheinlichkeit, mit der böswillige Quanten-Prover ein ungültiges Edge erfolgreich täuschen können, durch den Quantenwert eines nicht-lokalen CHSH$_{Q(2)}$-Spiels nach oben begrenzt ist. Durch die Verknüpfung der Soundness-Error des Protokolls mit diesem Spiel leiten sie eine rigorose obere Schranke für den Quanten-Soundness-Error $\delta$ ab.

Experimentelle Implementierung

Das Team implementierte ein Proof-of-Principle-Experiment unter Verwendung von:

• Hardware: Field-Programmable Gate Arrays (FPGAs) für niedrige Latenzzeiten und hochpräzise GPS-Zeitsynchronisationsserver (mit Atomuhren) zur Zeitmessung.
• Setup: Zwei Prover-Verifier-Paare, die 300 Meter voneinander entfernt sind (was einer Zeitseparation von $\tau = 1000$ ns entspricht).
• Graph: Ein drei-färbbarer Graph mit $|V| = 588$ Vertices und $|E| = 1097$ Edges.
• Ausführung: Das Experiment schloss alle erforderlichen interaktiven Runden in etwa 0,22 Sekunden ab.

Zentrale Beiträge

1. Effizientes asymmetrisches Protokoll: Die Autoren entwarfen ein asymmetrisches relativistisches GMW ZKP, das die Round-Komplexität von $O(|E|^4)$ (in früheren quanten-korrekten symmetrischen Protokollen) auf $O(|E|)$ reduziert. Dies wird durch die Nutzung von Zwei-Prover-Relativistischen Bit-Commitments innerhalb des GMW-Frameworks erreicht, wodurch Beweis und Konsistenzprüfungen simultan in einer einzigen Runde stattfinden können.
2. Beweis der Quanten-Korrektheit: Sie lieferten einen rigorosen Beweis für die Quanten-Korrektheit, indem sie die Betrugswahrscheinlichkeit von verschränkten Provern mit dem nicht-lokalen CHSH$_{Q(2)}$-Spiel verknüpften und so eine obere Schranke für den Soundness-Error ohne Abhängigkeit von rechnerischen Annahmen etablierten.
3. Experimentelle Realisierung: Sie führten das Protokoll erfolgreich über eine Separation von 300 Metern aus und demonstrierten damit, dass die erforderliche Laufzeit und der Randomness-Aufwand für eine reale Bereitstellung machbar sind.

Ergebnisse

• Round-Komplexität: Das Protokoll erfordert $m = 2k|E|$ Runden, um einen Soundness-Error von $e^{-k}$ zu erreichen. Für die experimentellen Parameter ($|E|=1097, k=100$) ergab dies etwa $2,2 \times 10^5$ Runden.
• Laufzeit: Das gesamte Experiment wurde in 0,22 Sekunden abgeschlossen. Im Gegensatz dazu hätte das vorherige quanten-korrekte symmetrische Protokoll [23] etwa $6,72 \times 10^4$ Jahre benötigt, um dieselbe Sicherheitsstufe mit demselben Graphen zu erreichen.
• Randomness-Kosten: Die gesamte Randomness-Kosten für das Experiment betrugen 430,81 MB. Das symmetrische Protokoll [23] hätte für dieselbe Aufgabe etwa $5,92 \times 10^9$ GB (5,92 Exabytes) benötigt.
• Sicherheit: Die Zeitdifferenzen $|t_1 - t_4|$ und $|t_2 - t_3|$ lagen konsistent unter dem 1000-ns-Schwellenwert, wodurch die relativistischen No-Signaling-Constraints selbst unter Berücksichtigung der GPS-Synchronisationsfehler erfüllt wurden.

Bedeutung und Behauptungen

Das Paper behauptet, dass diese Arbeit das starke Potenzial der Integration der speziellen Relativitätstheorie mit der Quantentheorie illustriert, um vertrauenslose kryptografische Systeme zu schaffen, die gegen Quantenangriffe sicher sind, ohne auf rechnerische Härteannahmen angewiesen zu sein.

Zentrale Behauptungen zur Bedeutung sind:

• Praktische Machbarkeit: Die Reduktion der Round-Komplexität von $O(|E|^4)$ auf $O(|E|)$ transformiert RZKPs von theoretischen Konstrukten in praktisch einsetzbare Technologien für reale Szenarien mit moderat großen Graphen.
• Unbedingte Sicherheit: Das Protokoll bietet Quanten-Korrektheit und Null-Wissen-Eigenschaften, die allein auf dem No-Signaling-Prinzip basieren, was es robust gegenüber zukünftigen Quantencomputer-Fortschritten macht.
• Skalierbarkeitspotenzial: Obwohl die asymmetrische Natur eine höhere Rechenlast auf ein Prover-Verifier-Paar ($V_1-P_1$) legt, argumentieren die Autoren, dass dieser Trade-off notwendig ist, um realistische Laufzeiten zu erreichen. Sie deuten an, dass das Protokoll auf alltäglichen Geräten wie Smartphones implementiert werden könnte.
• Zukünftige Anwendungen: Die Autoren heben potenzielle Anwendungen in privatsphärensensiblen Bereichen wie Blockchains, Smart Contracts, anonymem E-Voting und Online-Auktionen hervor. Sie merken zudem an, dass das Framework auf Zero-Knowledge Proofs of Knowledge (ZKPoK) zur Identitätsverifizierung erweitert werden kann.

Die Autoren bleiben hinsichtlich der Skalierbarkeit bescheiden und räumen ein, dass die praktische Bereitstellung in Glasfasernetzen noch Hürden wie die Verifizierung der präzisen Positionen der Prover und das Management der Rechenlast mit sich bringt, was sie als offene Probleme für die zukünftige Forschung identifizieren.