⚛️ quantum physics

Verifiable and Collusion-Resistant Multi-Party Quantum Private Set Operations

Dieses Paper schlägt ein verifizierbares und kollusionsresistentes Multi-Party-Quanten-Protokoll für die Private Set Intersection vor, das eine explizite Kardinalitätsprüfung ermöglicht, ohne dass ein vertrauenswürdiger Dritter die Ergebnisse interpretiert, indem es eine rotationsbasierte Quantenkonstruktion in Kombination mit Oblivious Linear Evaluation und Garbled Circuits nutzt, um lediglich offenzulegen, ob die Schnittmenge einen Schwellenwert erreicht.

Ursprüngliche Autoren: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

Veröffentlicht 2026-06-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich eine Gruppe von Freunden vor, von denen jeder eine geheime Liste seiner Lieblingsfilme besitzt. Sie wollen herausfinden, welche Filme sie alle mögen, ohne dass jemand seine vollständige Liste den anderen offenbaren muss. In der digitalen Welt wird dies als Private Set Intersection (PSI) bezeichnet.

Stellen Sie sich vor, diese Gruppe von Freunden ist riesig und sie nutzen einen superintelligenten, leistungsstarken Computer (nennen wir ihn den „Server“), um die Mathematik für sie zu erledigen. Das Problem? Was, wenn der Server ein wenig hinterhältig ist? Was, wenn der Server versucht, einen Blick auf die Listen zu werfen, oder was, wenn er mit einem der Freunde unter einer Decke steckt, um zu betrügen?

Dieses Paper präsentiert eine neue, hochtechnologische Lösung namens MP-QPSI (Multi-Party Quantum Private Set Intersection). Es nutzt die seltsamen Gesetze der Quantenphysik, um diese Probleme zu lösen. Hier ist die Funktionsweise, einfach erklärt:

Die Besetzung der Charaktere

Die Freunde (Teilnehmer): Sie besitzen die geheimen Listen. Sie sind „leichtgewichtig“, das heißt, sie verfügen nicht über leistungsstarke Computer; sie müssen nur ein wenig Quantenmagie anwenden, um ihre Daten zu sichern.
Der Server (Dritter/TP): Ein leistungsstarker Quantencomputer, der die ganze schwere Arbeit erledigt. Er wird angewiesen, die Berechnungen durchzuführen, aber das Protokoll geht davon aus, dass er versuchen könnte, zu schummeln oder zu spionieren.
Der Schiedsrichter (Vertrauenswürdige Instanz/TA): Eine neutrale Partei, die das Spiel aufbaut, Schlüssel verteilt und die Endergebnisse überprüft, um sicherzustellen, dass niemand geschummelt hat.

Das Kernproblem: Der „hinterhältige Server“

In älteren Versionen dieser Technologie wurde davon ausgegangen, dass der Server ehrlich ist oder zumindest nicht mit den Freunden unter einer Decke steckt. Wenn der Server und ein Freund kolludieren würden, könnten sie alle Geheimnisse stehlen. Dieses Paper behebt dieses Problem, indem es unmöglich macht, dass der Server und einige Freunde gemeinsam den Code knacken können.

Wie es funktioniert: Der „Quanten-Umschlag“ und die „Falle“

Stellen Sie sich den Prozess wie das Versenden eines Pakets durch einen sicheren Tunnel vor:

1. Die Daten versiegeln (Verschlüsselung)
Jeder Freund legt seine Filmliste in einen speziellen Quanten-Umschlag.

Das magische Schloss: Sie verwenden ein „Quantum One-Time Pad“. Stellen Sie sich ein Schloss vor, das seine Form jedes Mal zufällig ändert, wenn man es betrachtet. Für den Server sieht der Umschlag wie reines statisches Rauschen (zufälliges Flimmern) aus. Ohne den spezifischen Schlüssel ist es unmöglich zu erkennen, was sich darin befindet.
Die Fallen: Im Inneren des Umschlags verstecken die Freunde „Fallen“ – wie kleine Alarmglocken. Wenn der Server versucht, den Umschlag zu öffnen oder damit zu manipulieren, wird der Alarm ausgelöst.
Die geheime Aufteilung: Die Schlüssel zum Entsperren dieser Umschläge werden nicht von einer einzigen Person gehalten. Stattdessen schneidet der Schiedsrichter den Hauptschlüssel in Stücke und gibt jedem Freund ein Stück. Man benötigt eine bestimmte Anzahl von Freunden (einen „Schwellenwert“), um die Teile zusammenzusetzen und das Endergebnis zu öffnen. Dies verhindert, dass ein einzelner Freund mit dem Server zusammenarbeitet, um die Schlüssel zu stehlen.

2. Die Mathematik durchführen (Homomorphe Evaluation)
Der Server erhält all diese verschlossenen, verrauschten Umschläge.

Der magische Trick: Obwohl die Umschläge verschlossen sind, kann der Server die „UND“-Operation (das Finden der gemeinsamen Filme) durchführen, ohne sie jemals zu öffnen. Es ist wie ein Koch, der Zutaten in einem versiegelten, undurchsichtigen Beutel mischen und das Ergebnis sagen kann, ohne die Zutaten jemals gesehen zu haben.
Das Protokoll: Während der Server die Berechnungen durchführt, führt er ein detailliertes „Protokoll“ (eine Quittung) über jeden Schritt, den er unternommen hat.

3. Die Arbeit überprüfen (Verifizierung)
Sobald der Server fertig ist, sendet er das Ergebnis und das Protokoll zurück.

Die Freunde prüfen die Quittung: Die Freunde prüfen das Protokoll, um sicherzustellen, dass der Server die Regeln befolgt und nicht die Mathematik durch etwas anderes ersetzt hat.
Der Schiedsrichter prüft die Fallen: Der Schiedsrichter öffnet den finalen Umschlag. Zuerst prüft er die „Alarmglocken“ (Fallen). Wenn der Server versucht hat, zu spionieren oder zu betrügen, wurden die Fallen ausgelöst und der Schiedsrichter weiß es sofort.
Die finale Entsperrung: Wenn alles in Ordnung ist, führen die Freunde ihre Schlüsselstücke zusammen, um die endgültige Antwort freizuschalten: die Liste der Filme, die sie alle gemeinsam haben.

Warum ist das besonders?

Keine heimlichen Team-Bildungen: Selbst wenn der Server versucht, mit einigen Freunden zu kooperieren, kann er die Geheimnisse nicht stehlen, da der Schlüssel aufgeteilt ist. Er benötigt zu viele Freunde, um ihn zu entsperren.
Den Betrüger entlarven: Wenn der Server versucht, die falsche Mathematik durchzuführen oder die Daten einzusehen, wird ihn das „Fallen“-System und die Protokollprüfung erwischen. Die Freunde werden wissen, dass das Ergebnis gefälscht ist, und es ablehnen.
Flexibel: Das Paper zeigt, dass dieses System nicht nur zum Finden gemeinsamer Filme geeignet ist. Durch das Ändern einiger wenige „Schalter“ im „Schaltkreis“ kann es auch die Vereinigungsmenge (Union – alle einzigartigen Filme kombiniert) finden oder einfach nur zählen, wie viele Filme sie gemeinsam haben.

Das Fazit

Dieses Paper schlägt einen Weg vor, wie viele Menschen gemeinsam private Berechnungen durchführen können, indem sie einen leistungsstarken, potenziell nicht vertrauenswürdigen Computer nutzen. Es verwendet Quantenschlösser, um die Daten zu verbergen, aufgeteilte Schlüssel, um Kollusion zu verhindern, und Quantenfallen, um Betrüger zu überführen. Es ist wie ein hochkarätiges Pokerspiel, bei dem der Dealer (Server) die Karten zwar mischen kann, sie aber niemals sehen darf, und wenn er versucht zu betrügen, haben die Spieler einen unfehlbaren Weg, dies zu beweisen.

Technisches Resümee: Verifizierbare und kollusionsresistente Multi-Party Quantum Private Set Operations

1. Problemstellung

Private Set Operations (PSO), einschließlich Private Set Intersection (PSI) und Union (PSU), sind grundlegend für die sichere Mehrparteienberechnung (Secure Multiparty Computation, SMC). Während klassische kryptografische Lösungen existieren, bedrohen Quantenalgorithmen (z. B. Shor-Algorithmus) aktuelle zahlentheoretische Verfahren. Infolgedessen hat sich die Forschung in Richtung Quantum PSI (QPSI) verlagert.

Bestehende QPSI-Protokolle stehen jedoch vor erheblichen Einschränkungen:

Bedrohungsmodelle: Die meisten existierenden QPSI-Schemata setzen einen halb-ehrlichen vertrauenswürdigen Dritten (Trusted Third Party, TP) voraus oder basieren auf der Annahme, dass der TP nicht mit einem Teilnehmer kolludieren kann.
Kollusionsresistenz: Zuvor entwickelte Multi-Party QPSI (MP-QPSI) Protokolle scheitern oft an der Resistenz gegen eine Kollusion zwischen dem TP und einer Teilmenge der Teilnehmer, oder sie tolerieren lediglich die Korruption eines einzelnen Teilnehmers.
Verifizierbarkeit: Vielen Schemata fehlt ein Mechanismus, um zu verifizieren, dass der TP den vorgeschriebenen Quantenschaltkreis korrekt ausgeführt hat, was das System anfällig für bösartige Abweichungen macht.

2. Methodik

Die Autoren schlagen ein Multi-Party Quantum Private Set Intersection (MP-QPSI) Protokoll vor, das Verifiable Quantum Fully Homomorphic Encryption (vQFHE) mit Threshold Fully Homomorphic Encryption (TFHE) integriert. Das Protokoll operiert in einem Modell bestehend aus $n$ datenhaltenden Teilnehmern, einem leistungsfähigen Quanten-TP und einer vertrauenswürdigen Instanz (Trusted Authority, TA).

Kernkomponenten

Schwellenwert-Schlüsselverwaltung (TFHE):
- Der geheime Schlüssel zur Entschlüsselung wird unter Verwendung eines $(t, n)$ -Threshold-Secret-Sharing-Verfahrens unter den $n$ Teilnehmern aufgeteilt.
- Die Entschlüsselung erfordert die Zusammenarbeit von mindestens $t$ Teilnehmern. Dies stellt sicher, dass weder eine korrupte Teilmenge der Teilnehmer noch eine Kollusion zwischen dem TP und weniger als $t$ Teilnehmer den geheimen Schlüssel rekonstruieren oder private Eingaben erfahren kann.
Verifizierbare Quantenevaluierung (vQFHE):
- Das Protokoll nutzt die TrapTP-Konstruktion (aus [ADS+17]) als vQFHE-Schicht.
- Verschlüsselung: Teilnehmer kodieren ihre privaten Mengen in Quantenzustände mittels CSS-Codes, fügen Trap-Qubits ( $|0\rangle$ und $|+\rangle$ ) hinzu, wenden eine zufällige Permutation an und maskieren das Ergebnis mit einem Quantum One-Time Pad (QOTP). Die QOTP-Schlüssel werden unter TFHE verschlüsselt und mittels Message Authentication Codes (MAC) authentifiziert.
- Evaluierung: Der TP führt eine homomorphe Evaluierung eines Multi-Party-AND-Schaltkreises ( $C_{\text{AND}}$ ) auf den verschlüsselten Quantenzuständen durch. Der TP aktualisiert die verschlüsselten QOTP-Schlüssel homomorph und verbraucht „Gadgets“ (Magic States), um nicht-Clifford (T)-Gatter zu handhaben, folgend dem Garden-Hose-Modell.
- Verifizierung: Der TP genert ein klassisches Transkript (Log) der Evaluierung. Die Teilnehmer und die TA verifizieren dieses Log gegen die MACs, das Gate-Array und die Trap-Code-Messungen, um sicherzustellen, dass der TP nicht vom Zielschaltkreis abgewichen ist.
Protokollablauf:
- Phase 1 (Vorbereitung): Die TA generiert Schlüssel, sampelt Permutationen, bereitet T-Gate-Gadgets vor und verteilt die Secret Shares.
- Phase 2 (Verschlüsselung): Teilnehmer kodieren ihre Mengen in Quantenzustände, wenden Traps und QOTP an und senden die verschlüsselten Zustände sowie Schlüssel an den TP.
- Phase 3 (Evaluierung): Der TP führt den $C_{\text{AND}}$ -Schaltkreis homomorph aus, aktualisiert die Schlüssel und zeichnet ein Transkript auf.
- Phase 4 (Verifizierung & Entschlüsselung): Teilnehmer führen die klassische Verifizierung (MAC, Gate- und Transkript-Checks) und die Schwellenwert-Entschlüsselung durch, um die QOTP-Schlüssel zurückzugewinnen. Die TA führt die Quantenverifizierung (Trap-Checks) durch und entschlüsselt den finalen Zustand, um das Schnittmennisenergebnis zu verbreiten.

3. Zentrale Beiträge

Multi-Party Erweiterung: Die Autoren erweitern vQFHE auf ein Multi-Party-Szenario durch die Kombination mit TFHE, was es $n$ Parteien ermöglicht, Menge-Schnittmengen zu berechnen, ohne private Daten preiszugeben.
Kollusionsresistenz: Im Gegensatz zu bisherigen QPSI-Schemata ist dieses Protokoll resistent gegen eine Kollusion zwischen dem TP und bis zu $t-1$ Teilnehmern. Der Schwellenwert-Mechanismus stellt sicher, dass der geheime Schlüssel und die privaten Eingaben sicher bleiben, solange weniger als $t$ Parteien korrumpiert sind.
Verifizierbarkeit gegenüber einem böswilligen TP: Das Protokoll bietet semantische Sicherheit und Verifizierbarkeit. Es kann erkennen, ob ein böswilliger TP vom vorgeschriebenen Schaltkreis abweicht (z. B. durch Änderung des Gate-Arrays oder des Outputs) mittels einer Kombination aus klassischer Transkriptverifizierung und Quanten-Trap-Code-Checks.
Modulares Framework: Die Konstruktion wird als modulares Framework präsentiert. Die Autoren demonstrieren, wie man:
- Die Schaltwerkskomplexität reduziert (z. B. durch Verwendung von CCCZ-Gattern statt $C_nX$ , um die Anzahl der T-Gatter zu senken).
- Die Funktionalität auf Quantum Private Set Union (QPSU) erweitert, indem der AND-Schaltkreis mittels Open-Controlled-Operationen durch einen OR-Schaltkreis ersetzt wird.
- Unterschiedliche vQFHE-Instanziierungen austauscht, um verschiedene Effizienz-/Sicherheits-Abwägungen zu erreichen.

4. Ergebnisse und Analyse

Korrektheit: Die Autoren validierten das logische Multi-Party-AND-Gate mithilfe der IBM Quantum Platform und Qiskit. Simulationen bestätigten, dass die Ausgabeverteilung der idealen Wahrheitstabelle für die logische AND-Operation entspricht.
Sicherheitsbeweise:
- Privatsphäre: Das Protokoll ist gegenüber dem TP hinsichtlich der Quantenzustände informationstheoretisch sicher (aufgrund von QOTP und maximal gemischten Zuständen) und hinsichtlich der klassischen Daten computergestützt sicher (aufgrund von TFHE und MAC).
- Kollusion: Theorem 3 beweist, dass jede Koalition korrupter Teilnehmer (Größe $<t$ ), die mit dem TP kolludiert, keine Informationen über das Schnittmenresultat hinaus erhält.
- Verifizierbarkeit: Unter dem semantischen Sicherheitsmodell ( $\kappa$ -SEM-VER) ist das Protokoll als verifizierbar erwiesen. Ein hybrider Beweis zeigt, dass jede Abweichung durch den TP mit überwältigender Wahrscheinlichkeit erkannt wird.
Performance:
- Kommunikationskomplexität: Die Quantenkommunikationskosten betragen $O(n\kappa L)$ , wobei $n$ die Anzahl der Parteien, $\kappa$ der Sicherheitsparameter und $L$ die Set-Größe ist.
- Vergleich: Im Vergleich zu existierenden Schemata (z. B. [SMZ+15], [ZLS+20], [HZZ24]) ist das vorgeschlagene Protokoll das einzige, das Multi-Party-Szenarien mit sowohl PSI- als auch PSU-Fähigkeiten unterstützt und gleichzeitig Resistenz gegen TP-Teilnehmer-Kollusion und böswilliges TP-Verhalten bietet.

5. Bedeutung und Ansprüche

Das Paper beansprucht, einen signifikanten Fortschritt im Bereich der quantensicheren Berechnung zu leisten, indem es die Lücke der „TP-Teilnehmer-Kollusion“ schließt, die bestehende QPSI-Lösungen prägt.

Robustheit: Durch die Integration von TFHE erreicht das Protokoll ein Maß an Kollusionsresistenz, das in der Quanten-PSI bisher fehlte, und gewährleistet Sicherheit selbst dann, wenn der TP und eine Teilmenge der Teilnehmer konspirieren.
Minimierung des Vertrauens: Die Verifizierbarkeitsschicht ermöglicht es dem System, selbst dann sicher zu funktionieren, wenn der TP böswillig ist, wodurch die Notwendigkeit entfällt, der Ehrlichkeit des TP zu vertrauen – man vertraut lediglich seiner Rechenkapazität.
Flexibilität: Das modulare Design erlaubt es, das Framework für unterschiedliche Mengenoperationen (Union, Kardinalität) anzupassen und für unterschiedliche Hardware-Beschränkungen zu optimieren (z. B. Reduzierung der T-Gate-Komplexität).

Die Autoren räumen ein, dass das Protokoll zwar eine starke Sicherheit bietet, aber die klassische Overhead-Last mit sich bringt, die mit der TrapTP-basierten vQFHE verbunden ist. Zukünftige Arbeiten sollen die Untersuchung von Gadget-freiem T-Handling und weitere Optimierungen zur Senkung der klassischen Kommunikationskosten untersuchen.