Private Proofs of When and Where

Dieses Paper stellt das Konzept der Null-Wissen-Positionsverifikation vor, das es ermöglicht, komplexe Aussagen über vergangene oder zukünftige Aufenthaltsorte zu beweisen, ohne die genaue Position preiszugeben, und zeigt, wie dies mithilfe von Standard-Positionsverifikation und postquantensicheren Einwegfunktionen realisiert werden kann.

Das Wesentliche

Das große Problem: "Wo bist du?" ohne "Was machst du?"

Stell dir vor, du möchtest jemandem beweisen, dass du dich zu einem bestimmten Zeitpunkt an einem bestimmten Ort befindest. Vielleicht musst du einem Richter beweisen, dass du gestern um 12 Uhr nicht am Tatort warst, oder einem Staat beweisen, dass eine Waffe sich nie außerhalb der Landesgrenzen befand.

Das ist das Ziel der Positionsverifizierung.

Das klassische Problem:
In der klassischen Welt (ohne Quantencomputer) ist das fast unmöglich sicher zu machen. Ein Betrüger könnte einfach mehrere Freunde an verschiedenen Orten postieren und diese wie ein "Puppenspiel" koordinieren. Sie würden so tun, als wären sie alle an einem Ort, obwohl sie eigentlich weit verteilt sind. Es ist, als würde man versuchen, zu beweisen, dass man in einer einzigen Zelle sitzt, während man eigentlich in drei verschiedenen Zellen gleichzeitig steht, aber alle gleichzeitig sprechen.

Die Quanten-Lösung:
Die Wissenschaftler nutzen Quantenphysik (insbesondere das Prinzip, dass man Quantenzustände nicht kopieren kann), um Betrug zu erschweren. Wenn man Quanten-Nachrichten schickt, können die Betrüger sie nicht einfach abfangen und weiterleiten, ohne sie zu zerstören. Das macht die Positionsverifizierung sicher.

Das neue Problem: Die Privatsphäre
Aber hier kommt das große "Aber": Selbst wenn die Verifizierung sicher ist, verrät sie dem Richter oder der Polizei genau, wo du warst.

• Szenario: Du willst beweisen, dass du gestern nicht bei der Bank warst (weil du dort nicht warst).
• Das Problem: Wenn du den Beweis erbringst, verrätst du dem Richter vielleicht auch, dass du stattdessen bei deiner Freundin warst. Du willst nur das "Nein" beweisen, nicht dein "Ja" zu einem anderen Ort.

Das ist wie bei einem Sicherheitscheck am Flughafen: Du willst beweisen, dass du keine Waffe hast, ohne dem Sicherheitsbeamten deine gesamte Lebensgeschichte und alle deine Tascheninhalte zu zeigen.

Die Lösung: "Geheime Zeit-Ort-Verträge"

Die Autoren dieses Papiers haben eine neue Methode entwickelt, die Zero-Knowledge Position Verification (Null-Wissen-Positionsverifizierung) genannt wird.

Stell dir das so vor:

1. Der "Geheime Zeit-Ort-Vertrag" (Position Commitment)

Stell dir vor, du hast einen magischen Briefkasten.

• Der Schritt "Commit" (Verpflichten): Du gehst an einen Ort (z. B. in den Park) und wirfst einen verschlüsselten Brief in den Briefkasten. In diesem Brief steht: "Ich war um 12 Uhr im Park." Aber der Brief ist mit einem Schlüssel verschlossen, den nur du hast. Niemand sonst sieht, was drin steht.
• Das Besondere: Während du den Brief in den Briefkasten wirfst, simulierst du gleichzeitig, als würdest du alle anderen Orte der Stadt besuchen. Du schickst verschlüsselte "Pseudo-Nachrichten" an alle Verifizierer, die so aussehen, als kämen sie von überall her. Da die Nachrichten verschlüsselt sind, können die Verifizierer nicht unterscheiden, ob du wirklich im Park warst oder nur so getan hast.
• Der Schritt "Reveal" (Enthüllen): Später, wenn du es beweisen musst, gibst du den Schlüssel heraus. Dann öffnen die Verifizierer den Brief und sehen: "Ah, er war tatsächlich im Park."

Das Geniale daran: Solange der Schlüssel nicht herausgegeben wird, wissen die Verifizierer nur, dass irgendein Brief im Briefkasten ist, aber nicht, was darin steht oder woher er kam.

2. Der "Beweis ohne Enthüllung" (Zero-Knowledge)

Jetzt kommt der zweite Teil. Angenommen, du willst dem Richter beweisen: "Ich war gestern nicht beim Tatort."

• Du hast deinen "Geheimen Zeit-Ort-Vertrag" (den verschlüsselten Brief) erstellt.
• Statt den Brief zu öffnen und zu zeigen "Ich war im Park", nutzt du ein mathematisches Zaubertrick-Verfahren (einen Zero-Knowledge-Beweis).
• Du sagst dem Richter: "Ich kann beweisen, dass der Inhalt meines verschlüsselten Briefes irgendein Ort ist, der nicht der Tatort ist."
• Der Richter prüft deine Mathematik. Er sieht, dass die Logik stimmt. Er ist überzeugt, dass du nicht am Tatort warst.
• Aber: Er sieht niemals, wo du tatsächlich warst. Er weiß nur, dass es ein Ort war, der sicher nicht der Tatort ist.

Die Analogie: Der unsichtbare Tanz

Stell dir vor, du tanzst in einem dunklen Raum mit vielen Lichtern (den Verifizierern).

• Normaler Beweis: Du schaltest das Licht an. Jeder sieht genau, wo du stehst.
• Unser neuer Beweis: Du trägst eine spezielle Maske und tanzst in einem Raum, der mit Tausenden von unsichtbaren Schatten gefüllt ist. Die Verifizierern sehen nur, dass irgendeine Silhouette im Raum tanzt und dass diese Silhouette nicht an der Stelle steht, wo der Mord geschah.
• Du beweist die Abwesenheit am Tatort, ohne jemals zu zeigen, wo du tatsächlich tanztest.

Warum ist das wichtig?

1. Schutz vor Überwachung: Stell dir vor, Bodyguards nutzen Fitness-Apps (wie Strava), um ihre Bewegung zu tracken. Das hat versehentlich die Bewegungen von Staatschefs verraten (wie in der Einleitung erwähnt). Mit dieser Technik könnten sie beweisen: "Wir waren heute sicher im Schutzgebiet", ohne dass die App verrät, wo genau im Schutzgebiet sie waren.
2. Politische Verträge: Länder könnten beweisen, dass sie keine Atomwaffen in der Antarktis haben, ohne ihre gesamten Militärbasen und Truppenbewegungen offenzulegen.
3. Alibis: Man könnte einem Richter beweisen, dass man nicht am Tatort war, ohne zu verraten, wo man stattdessen war (vielleicht bei einem Treffen, das man geheim halten möchte).

Zusammenfassung

Die Autoren haben einen Weg gefunden, Quantenphysik und moderne Kryptographie zu mischen, um zwei Dinge gleichzeitig zu erreichen:

1. Sicherheit: Man kann nicht lügen, wo man war (dank Quantenphysik).
2. Privatsphäre: Man muss nicht verraten, wo man war, sondern nur beweisen, dass man nicht an einem bestimmten, verbotenen Ort war.

Es ist wie ein magischer Siegel, der garantiert, dass die Wahrheit gesagt wird, ohne dass die Geheimnisse des Sprechers preisgegeben werden.

Technische Zusammenfassung

1. Problemstellung und Motivation

Hintergrund:
Positionsverifikationsprotokolle (Position Verification, PV) ermöglichen es einer Entität (dem „Beweiser" oder Prover), einer Gruppe von Verifizierern (Verifiers) physisch zu beweisen, dass sie sich zu einem bestimmten Zeitpunkt an einem bestimmten Ort befindet. Während klassische PV-Protokolle aufgrund von Angriffen durch kolludierende Gegner (die Signale manipulieren können) als unsicher gelten, bieten Quanten-Protokolle (QPV) aufgrund physikalischer Prinzipien wie der Unklonbarkeit von Quantenzuständen und der Unsicherheitsrelation theoretische Sicherheit.

Das Kernproblem:
Bestehende QPV-Protokolle offenbaren die exakte Position des Beweisers. In vielen Anwendungen ist dies jedoch unerwünscht oder gefährlich. Beispiele sind:

• Der Nachweis, dass man sich nicht an einem Tatort befand (Alibi), ohne die tatsächliche Position preiszugeben.
• Die Einhaltung von Verträgen (z. B. Atomwaffenverbotszonen), ohne die genaue Position von Geräten zu verraten.
• Der Schutz von Bewegungsprofilen (wie im Fall von Fitness-Apps, die die Bewegungen von Staatschefs preisgaben).

Die zentrale Forschungsfrage lautet: Können Positionsverifikationsprotokolle so gestaltet werden, dass sie Zero-Knowledge (Null-Wissen) sind? Das bedeutet, der Verifizierer soll nur davon überzeugt werden, dass eine bestimmte Aussage über die Position wahr ist (z. B. „Ich war gestern um 12 Uhr nicht in Region L"), ohne weitere Informationen über den tatsächlichen Aufenthaltsort zu erhalten.

2. Methodik und Technische Konzepte

Die Autoren führen ein neues primitives Konzept ein, das als Baustein für ihre Lösung dient: das Positions-Commitment (Position Commitment).

A. Positions-Commitment

Dies ist ein Protokoll, bei dem ein Beweiser seine räumlich-zeitliche Position $(L, t)$ in einem Commitment-Phase festlegt, ohne sie sofort preiszugeben. Später kann er das Commitment öffnen (Reveal-Phase), um zu beweisen, dass er sich zu diesem Zeitpunkt tatsächlich an diesem Ort befand.

• Hiding (Versteckung): Während der Commit-Phase lernen die Verifizierer nichts über die Position.
• Binding (Bindung): Der Beweiser kann sich später nicht auf eine andere Position festlegen; er muss physikalisch an dem Ort gewesen sein, den er angibt. Dies ist stärker als bei klassischen Commitments, da es eine physikalische Präsenz erfordert.

Konstruktion des Commitments:
Das Commitment wird aus zwei Komponenten aufgebaut:

1. Sichere Singleton-Positionsverifikation: Ein existierendes, sicheres QPV-Protokoll für einen einzelnen Punkt (z. B. das $f$-BB84-Protokoll).
2. Post-Quantum Kryptographie: Einwegfunktionen (OWF), die für Verschlüsselung und Commitments genutzt werden.

Ablauf (Encrypt-Then-Verify):

• Der Beweiser plant, sich an einem geheimen Ort $(L^*, t^*)$ innerhalb eines zulässigen Bereichs $S$ aufzuhalten.
• Er initiiert eine Sitzung, in der er mit den Verifizierern interagiert.
• Um seine Position zu verbergen, führt er parallel Simulationen der Positionsverifikationsprotokolle für alle möglichen Punkte in $S$ durch.
• Für den tatsächlichen Ort berechnet er die korrekte Antwort und verschlüsselt sie. Für alle anderen (falschen) Orte sendet er verschlüsselte Dummy-Nachrichten (oder leere Antworten), die jedoch so getimed sind, dass sie die Verifizierer täuschen.
• Der Beweiser verschlüsselt alle seine Antworten mit einem geheimen Schlüssel $sk$.
• Zu Beginn des Protokolls commitet er diesen Schlüssel $sk$ (mithilfe eines klassischen Commitments).
• Die Verifizierer erhalten einen Strom verschlüsselter Nachrichten, deren Zeitstempel konsistent mit der Annahme sind, dass ein Beweiser an jedem Punkt von $S$ sein könnte.
• In der Reveal-Phase gibt der Beweiser $sk$ und seine tatsächliche Position frei. Die Verifizierer entschlüsseln die Nachrichten und prüfen, ob nur für die angegebene Position die Verifikationsbedingungen erfüllt sind.

B. Zero-Knowledge Positionsverifikation (ZK-PV)

Um eine ZK-Beweisführung für eine beliebige Region $R$ (z. B. „Ich war in Region R") zu erreichen, kombinieren die Autoren das Positions-Commitment mit einem klassischen Zero-Knowledge-Beweis für NP-Sprachen.

1. Der Beweiser erstellt ein Positions-Commitment für seine tatsächliche Position.
2. Er führt einen Zero-Knowledge-Beweis (basierend auf OWF) dafür, dass das Commitment eine Öffnung besitzt, deren resultierende Position in der gewünschten Region $R$ liegt.
3. Da das Commitment „hiding" ist und der ZK-Beweis keine zusätzlichen Informationen preisgibt, bleibt die exakte Position geheim.

3. Wichtige Beiträge

1. Formalisierung von Zero-Knowledge Positionsverifikation: Die Autoren definieren ZK-PV präzise mittels einer simulationsbasierten Sicherheitsdefinition. Sie zeigen, dass die Sicht der Verifizierer simuliert werden kann, ohne die genaue Position des Beweisers zu kennen.
2. Einführung des „Position Commitment" Primitives: Dies ist ein neues kryptographisches Werkzeug, das es erlaubt, sich physikalisch an einem Ort zu verpflichten, ohne diesen sofort offenzulegen. Es verbindet die Bindungseigenschaften klassischer Commitments mit der Positionsicherheit von QPV.
3. Konstruktionssatz: Sie beweisen, dass ZK-PV aus sicheren Singleton-PV-Protokollen (gegenüber Angreifern mit begrenzter Verschränkung) und post-quantum One-Way Functions konstruiert werden kann.
4. Optimierung: Sie stellen eine optimierte Version des Protokolls vor, die für Verifizierer mit rein klassischen, broadcast-basierten Nachrichten effizienter ist und die rechnerische Last reduziert.

4. Ergebnisse und Sicherheit

• Hauptsatz (Theorem 1.1): Unter der Annahme der Existenz von post-quantum One-Way Functions und „netten" (nice) Singleton-PV-Protokollen (die gegen Angreifer mit bis zu $E$ verschränkten Qubits sicher sind), existiert ein Zero-Knowledge Positionsverifikationsprotokoll für jede endliche Menge von Raumzeit-Punkten. Dieses Protokoll ist sicher gegen Angreifer, die bis zu $E/2$ verschränkte Qubits teilen.
• Sicherheitsgarantien:
  • Vollständigkeit: Ein ehrlicher Beweiser wird akzeptiert.
  • Positions-Sicherheit: Kolludierende Angreifer, die sich nicht in der Region $R$ befinden, können das Protokoll nur mit vernachlässigbarer Wahrscheinlichkeit erfolgreich durchlaufen.
  • Zero-Knowledge: Ein Simulator kann die Sicht der Verifizierer erzeugen, ohne die wahre Position zu kennen. Dies gilt für semi-ehrliche Verifizierer (die das Protokoll korrekt ausführen, aber versuchen, mehr zu lernen).
• Annahmen: Die Sicherheit basiert auf der Unmöglichkeit, Quantenzustände zu klonen (für die PV-Komponente) und der Schwierigkeit, One-Way Functions umzukehren (für die Verschlüsselung und Commitments).

5. Bedeutung und Ausblick

Bedeutung:
Dieses Paper schließt eine wichtige Lücke zwischen Quantenkryptographie und Privatsphäre. Es zeigt, dass man nicht nur dass man an einem Ort ist beweisen kann, sondern auch komplexe Aussagen darüber (z. B. „Ich war nicht dort"), ohne die genaue Geolokation zu verraten. Dies hat weitreichende Implikationen für:

• Datenschutz in mobilen Anwendungen.
• Verifikation von Compliance bei internationalen Verträgen (z. B. Nichtverbreitung von Atomwaffen).
• Forensik und Alibis.

Grenzen und zukünftige Richtungen:

• Semi-ehrliche Verifizierer: Die aktuelle Konstruktion garantiert Zero-Knowledge nur gegenüber Verifizierern, die das Protokoll korrekt ausführen. Gegenüber bösartigen Verifizierern, die gezielt Richtungsstrahlen senden, um die Position zu testen („Poke-around-in-the-dark"-Angriff), ist das Protokoll anfällig, da ein Beweiser nicht unterscheiden kann, ob eine Nachricht gerichtet oder broadcast war.
• Zukünftige Arbeit: Die Autoren schlagen vor, Modelle zu untersuchen, in denen Verifizierer nur Broadcast-Nachrichten senden dürfen oder in denen eine Mehrheit von Verifizierern als ehrlich angenommen wird, um auch gegen bösartige Verifizierer Zero-Knowledge zu erreichen.
• Praktikabilität: Die Modelle gehen von perfekten Uhren und instantaner Berechnung aus. Die Übertragung auf reale Umgebungen mit Ungenauigkeiten ist ein wichtiger nächster Schritt.

Zusammenfassend legt dieses Werk den Grundstein für eine neue Ära privater, quantensicherer Ortsverifikation, die die Privatsphäre der Nutzer schützt, während gleichzeitig die Integrität der Positionsbehauptungen gewahrt bleibt.