Quantum Private Intersection Based on Single Qubits

Das große Ganze: Das Problem des „Geheimen Clubs“

Stellen Sie sich zwei Personen vor, Alice und Bob, die jeweils eine geheime Liste ihrer Lieblingshobbys haben.

• Alices Liste: {Wandern, Kochen, Schach, Gartenarbeit}
• Bobs Liste: {Schach, Schwimmen, Gartenarbeit, Malen}

Sie wollen wissen: „Welche Hobbys mögen wir beide?“ (Die Antwort ist: Schach und Gartenarbeit).

Sie haben jedoch ein Problem:

1. Sie wollen sich nicht gegenseitig ihre gesamten Listen zeigen (Alice möchte nicht, dass Bob weiß, dass sie Kochen mag; Bob möchte nicht, dass Alice weiß, dass er Schwimmen mag).
2. Sie vertrauen einander nicht genug, um ihre Listen einfach über das Internet zu senden, da ein Hacker (nennen wir sie Eve) die Daten stehlen könnte.
3. Sie wollen auch nicht auf einen „Vermittler“ angewiesen sein, der betrügen oder einen Blick auf ihre Listen werfen könnte.

Dies ist das Private Set Intersection (PSI) Problem. Die Arbeit schlägt einen neuen Weg vor, dieses Problem mithilfe der Quantenphysik (speziell von einzelnen Lichtteilchen namens „Qubits“) zu lösen, um absolute Privatsphäre und Fairness zu gewährleisten.

---

Die Besetzung

• Alice & Bob: Die zwei Personen mit den geheimen Listen.
• Charlie: Ein „semi-ehrlicher“ Dritter (wie ein Schiedsrichter). Er hält sich strikt an die Regeln, könnte aber versuchen, einen Blick auf die Daten zu werfen, wenn er kann. Er ist notwendig, um ihnen zu helfen, die Antwort zu berechnen, ohne dass sie direkt miteinander kommunizieren müssen.
• Eve: Die Lauscherin, die versucht, die Geheimnisse zu stehlen.

Das magische Werkzeug: Die „Quantenmünze“

Anstatt Listen auf Papier zu schreiben, verwenden Alice und Bob Quantenmünzen (Single Qubits).

• Eine normale Münze hat Kopf oder Zahl.
• Eine „Quantenmünze“ kann Kopf, Zahl oder eine Superposition (Überlagerung) von beidem sein.
• Die goldene Regel der Quantenphysik: Wenn man eine Quantenmünze betrachtet, um zu sehen, was sie ist, verändert man sie. Wenn man sie auf die falsche Art betrachtet, wird sie zu zufälligem Rauschen.

Die Arbeit verwendet zwei spezielle „Züge“ (Unitary Operators) an diesen Münzen:

1. Zug U1: Die Münze umdrehen (Kopf wird zu Zahl, Zahl wird zu Kopf).
2. Zug U2: Ein komplexerer Flip, der, wenn man ihn zweimal ausführt, dasselbe bewirkt wie ein einziger Zug von U1.

---

Wie das Protokoll funktioniert (Das Spiel)

Das Spiel findet in zwei Runden (Phasen) statt, um die gemeinsamen Hobbys zu finden.

Phase 1: Die „Wer hat es?“-Runde

Ziel: Herauszufinden, welche Artikel in mindestens einer der Listen enthalten sind (Die Vereinigung).

1. Charlie bereitet eine lange Reihe von Quantenmünzen vor, die sich jeweils in einem zufälligen Zustand befinden (wie Kopf, Zahl oder rotierend). Er versteckt einige „Lockmünzen“ (falsche Münzen) in der Reihe, um Spione zu fangen.
2. Charlie sendet die Reihe an Alice.
3. Alice überprüft die Lockmünzen, um sicherzustellen, dass niemand spioniert. Wenn es sicher ist, schaut sie auf ihre geheime Liste.
   • Wenn sie ein Hobby auf ihrer Liste hat, führt sie den Zug U1 (Flip) auf diese spezifische Münze aus.
   • Wenn sie es nicht hat, lässt sie die Münze unverändert.
4. Alice mischt die Reihenfolge der Münzen (damit Charlie nicht erkennen kann, welche Münze zu welchem Hobby gehört) und sendet sie an Bob.
5. Bob überprüft die Lockmünzen. Wenn es sicher ist, schaut er auf seine Liste.
   • Wenn er das Hobby hat, führt er den Zug U1 (Flip) auf diese Münze aus.
   • Wenn er es nicht hat, lässt er die Münze unverändert.
6. Bob sendet die Münzen zurück an Charlie.

Das Ergebnis:

• Wenn keiner das Hobby hatte: Die Münze wurde nie gedreht. (Zustand: Original)
• Wenn nur einer es hatte: Die Münze wurde einmal gedreht. (Zustand: Gedreht)
• Wenn beide es hatten: Die Münze wurde zweimal gedreht. (Zustand: Zurück zum Original, da zweimaliges Drehen sich gegenseitig aufhebt).

Charlie misst die Münzen. Er kann nun sehen, welche Hobbys in mindestens einer Liste sind (diejenigen, die anders aussehen als zu Beginn) und welche in beiden oder keinen (diejenigen, die gleich aussehen wie zu Beginn). Er erstellt eine Kurzliste von „Kandidaten“, weiß aber noch nicht, wem sie gehören.

Phase 2: Die „Wem gehört es?“-Runde

Ziel: Die Kurzliste filtern, um die exakten Übereinstimmungen zu finden (Die Schnittmenge).

1. Charlie nimmt die „Kandidaten“-Münzen und sendet sie zurück an Alice.
2. Alice verwendet einen anderen Zug, Zug U2, auf die Münzen, die ihr gehören.
3. Bob erhält sie und verwendet ebenfalls Zug U2 auf die Münzen, die ihm gehören.
4. Charlie erhält sie zurück und misst sie erneut.

Die magische Logik:

• Wenn keiner es in Phase 1 besaß, tun sie in Phase 2 nichts. Die Münze bleibt gleich.
• Wenn beide es in Phase 1 besaßen, führen beide in Phase 2 den Zug U2 aus. Zweimal Ausführen von U2 ist mathematisch gesehen dasselbe wie ein einziger Zug U1. Dies dreht die Münze!
• Charlie sieht den Flip. Er weiß: „Diese Münze wurde in Phase 2 gedreht, was bedeutet, dass sowohl Alice als auch Bob sie berührt haben.“

Die endgültige Antwort:
Charlie sagt Alice und Bob: „Die Hobbies, die diesen gedrehten Münzen entsprechen, sind die, die ihr beide teilt.“

---

Warum ist dies sicher? (Der „Spion“-Beweis)

Die Arbeit behauptet, dass dies gegen zwei Arten von böswilligen Akteuren sicher ist:

1. Der externe Spion (Eve):
Eve versucht, die Münzen abzufangen.

• Die Falle: Charlie versteckt „Lockmünzen“. Eve weiß nicht, welche die echten und welche die Lockmünzen sind.
• Der Fehler: Um eine Münze zu lesen, muss Eve raten, wie sie danach schauen muss. Wenn sie falsch rät, verändert sie den Zustand der Münze.
• Die Konsequenz: Wenn Alice und Bob die Lockmünzen überprüfen, werden sie sehen, dass sich die Münzen verändert haben. Sie wissen, dass Eve da war, brechen das ganze Spiel ab und beginnen von vorn. Die Arbeit berechnet, dass mit genügend Lockmünzen die Chance, dass Eve unentdeckt bleibt, praktisch null ist.

2. Der betrügerische Teilnehmer (Charlie, Alice oder Bob):

• Charlie (Der Schiedsrichter): Er sieht die Münzen, aber er kennt die Reihenfolge nicht, weil Alice und Bob sie gemischt haben. Er kann nicht erkennen, wer eine Münze gedreht hat, sondern nur, dass sie gedreht wurde. Er kann nicht die gesamte Liste stehlen.
• Alice & Bob: Sie können die Liste des anderen nicht sehen, weil sie den ursprünglichen Zustand der Münzen nicht kennen, die Charlie vorbereitet hat. Wenn sie versuchen, die Münzen vorzeitig zu messen, erhalten sie nur zufälliges Rauschen.

Warum ist diese Arbeit besonders? (Der „Effizienz“-Anspruch)

Frühere Quantenlösungen waren wie der Versuch, ein Haus mit einem riesigen, komplexen Kran zu bauen (unter Verwendung schwerer Verschränkung und komplexer Mathematik). Sie waren schwer zu bauen und teuer.

Diese Arbeit schlägt vor, Single-Qubit-Operationen (einfache Flips) zu verwenden.

• Analogie: Anstatt eines riesigen Krans verwenden sie ein einfaches Handwerkzeug.
• Vorteil: Es benötigt weniger „Ressourcen“ (weniger Teilchen), erfordert einfachere Ausrüstung und ist viel leichter mit der heutigen Technologie umsetzbar.
• Fairness: Im Gegensatz zu einigen älteren Methoden, bei denen nur eine Person die Antwort erhielt, stellt diese Methode sicher, dass sowohl Alice als auch Bob die Liste der gemeinsamen Hobbys zur gleichen Zeit erhalten.

Der „Labortest“ (Simulation)

Die Autoren haben nicht nur die Theorie aufgeschrieben; sie haben eine virtuelle Version dieses Spiels mit IBMs Qiskit (einem Quantencomputer-Simulator) gebaut.

• Sie simulierten ein kleines Beispiel mit den Zahlen 0 bis 7.
• Alice hatte {1, 3, 5, 7}.
• Bob hatte {2, 3, 4, 7}.
• Der Computer durchlief die „Flip“- und „Shuffle“-Schritte.
• Ergebnis: Der Computer identifizierte korrekt {3, 7} als die gemeinsamen Elemente, was beweist, dass die Mathematik in der Praxis funktioniert.

Zusammenfassung

Diese Arbeit präsentiert einen neuen, einfacheren und faireren Weg für zwei Personen, ihre gemeinsamen Geheimnisse mithilfe der Quantenphysik zu finden. Sie nutzt einfache „Münzwürfe“ auf einzelnen Teilchen, verbirgt die Daten mit „Lockfallen“, um Spione zu fangen, und stellt sicher, dass selbst der Schiedsrichter nicht betrügen kann. Sie wurde auf einem Computersimulator getestet und funktioniert perfekt.