⚛️ quantum physics

Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

Dieses Paper schlägt ein quantenbasierter Multi-Party-Threshold-Private-Set-Intersection-Protokoll mit explizitem Kardinalitätstest vor, welches eine rotationsbasierte Einzelphotonen-Konstruktion und kryptographische Primitive nutzt, um es einer dritten Partei zu ermöglichen, Messungen durchzuführen, ohne die Ergebnisse zu interpretieren, während gleichzeitig sicher nur offengelegt wird, ob die Schnittmenge einen Schwellenwert erreicht.

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

Veröffentlicht 2026-06-29

📖 6 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, die jeweils eine geheime Liste ihrer Lieblingsfilme haben. Sie wollen wissen: „Sind wir uns über mindestens drei Filme einig?“

Wenn die Antwort Ja lautet, wollen sie die Liste dieser drei Filme sehen.
Wenn die Antwort Nein lautet, wollen sie gar nichts wissen – nicht einmal, wie viele Filme sie tatsächlich gemeinsam hatten.

Dies ist das Problem des Threshold Private Set Intersection (TPSI). Das Paper schlägt einen neuen Weg vor, dies mithilfe von Quantenmechanik (speziell einzelnen Photonen aus Licht) und kluger Mathematik zu lösen, wobei sichergestellt wird, dass selbst die Person, die das Experiment durchführt, nicht betrügen oder einen Blick auf die Geheimnisse werfen kann.

So funktioniert die Lösung des Papers, aufgeschlüsselt in einfache Konzepte:

1. Das Problem mit alten Methoden

In früheren Quantenversuchen verließ sich die Gruppe auf einen „Schiedsrichter“ (einen Dritten, kurz „Third Party“ oder TP), um die Übereinstimmungen zu zählen.

Der Fehler: Der Schiedsrichter zählte die Übereinstimmungen, verglich diese Zahl mit dem Schwellenwert (z. B. „Ist 3?“) und entschied dann, was er der Gruppe mitteilt.
Das Risiko: Dies bedeutete, dass der Schiedsrichter die exakte Anzahl der Übereinstimmungen sah. Wenn die Gruppe nur 2 Übereinstimmungen hatte, wusste der Schiedsrichter das. Aber die Gruppe wollte nur wissen, ob sie genug hatte (3 oder mehr), nicht die exakte Anzahl. Es ist, als würde man einem Richter fragen: „Ist der Angeklagte schuldig?“, aber der Richter muss zuerst eine vollständige Biografie des Verbrechens schreiben, bevor er antworten kann.

2. Die neue Lösung: Der „blind geflickte Schiedsrichter“

Die Autoren entwickelten ein Protokoll, bei dem der Schiedsrichter die Messungen durchführt, aber bezüglich der Bedeutung der Ergebnisse blind ist.

Das Setup: Der geheime Code

Bevor das Experiment beginnt, vereinbaren die Freunde (Teilnehmer) untereinander einen geheimen Code. Sie mischen auch ihre echten Filmlisten mit einigen „Dekoy“-Fake-Listen (Ankern), die der Schiedsrichter nicht kennt.

Der Versteck-Schlüssel: Sie vertauschen die Positionen ihrer Filme mithilfe eines geheimen Schlüssels. Für den Schiedsrichter sehen die Listen wie zufälliges Rauschen aus.
Der Flip: Sie vereinbaren einen geheimen „Flip“ (wie ein geheimes Handshake), der die Bedeutung der Ergebnisse verändert. Wenn ein Licht „An“ geht, kann es je nach diesem geheimen Flip eigentlich „Aus“ bedeuten.

Der Quantentanz (Die Rotation)

Das Experiment nutzt Photonen (Lichtteilchen) als Boten.

Der Schiedsrichter bereitet eine Linie von Photonen vor und sendet sie an den ersten Freund.
Freund 1 betrachtet seine geheime Liste. Wenn er an einer bestimmten Stelle einen bestimmten Film hat, gibt er dem Photon eine winzige „Drehung“ (Rotation). Wenn er ihn nicht hat, lässt er es unverändert. Er fügt auch eine geheime „Masken“-Rotation hinzu, die nur er und der Schiedsrichter kennen.
Die Kette: Die Photonen reisen zu Freund 2, dann zu Freund 3 und so weiter. Jeder Freund fügt seine eigene Drehung basierend auf seiner geheimen Liste hinzu.
Die Rückkehr: Die Photonen kehren zum Schiedsrichter zurück.

Die Magie der „Verborgenen Labels“

Wenn die Photonen zurückkehren, entfernt der Schiedsrichter seine eigenen Masken und misst das Licht.

Das Ergebnis: Der Schiedsrichter sieht ein Muster von „Gleich“ oder „Gegensätzlich“ hellem Licht.
Der Clou: Da durch den von den Freunden vereinbarten geheimen „Flip“ der Schiedsrichter nicht verstehen kann, was das Muster bedeutet. Ein „Gleich“-Ergebnis kann je nach einem geheimen Bit, das nur die Freunde kennen, „Übereinstimmung“ oder „Keine Übereinstimmung“ bedeuten. Der Schiedsrichter hat die Daten, aber sie sehen für ihn wie Kauderwelsch aus.

3. Die abschließende Prüfung: Die „Blinde Abstimmung“

Nun müssen die Freunde und der Schiedsrichter entscheiden: „Haben wir den Schwellenwert erreicht?“, ohne dass der Schiedsrichter die exakte Anzahl erfährt.

Der Mathe-Trick (OLE): Sie verwenden ein kryptografisches Werkzeug namens Oblivious Linear Evaluation. Denken Sie an dies als einen sicheren Taschenrechner, in den der Schiedsrichter seine „Kauderwelsch“-Zahlen eingibt und die Freunde ihre „geheimen Schlüssel“.
Der Garbled Circuit: Sie führen ein winziges, verschlüsseltes Computerprogramm (einen Garbled Circuit) aus. Dieses Programm addiert die Zahlen intern auf.
Die Ausgabe: Das Programm gibt nur ein einziges Bit aus: 1 (Ja, wir haben genug Übereinstimmungen) oder 0 (Nein, wir haben nicht genug).
- Wenn die Antwort 1 ist, enthüllen die Freunde den geheimen Schlüssel, um das „Kauderwelsch“-Muster des Schiedsrichters zu dekodieren, und sie sehen die passenden Filme.
- Wenn die Antwort 0 ist, werfen sie alles weg. Der Schiedsrichter erfährt nie die exakte Anzahl der Übereinstimmungen, sondern nur, dass sie nicht hoch genug war.

4. Warum dies sicher ist (Sicherheit)

Das Paper beweist drei Hauptpunkte der Sicherheit:

Keine Lauscher: Wenn ein Spion versucht, die Photonen abzufangen, werden die „Dekoy“-Lichter (die der Spion nicht kennt) die Veränderung anzeigen, was alle warnt, dass die Leitung angezapft wurde.
Der Schiedsrichter ist ehrlich, aber neugierig: Selbst wenn der Schiedsrichter versucht zu betrügen oder ausgeklügelte Quantentricks anzuwenden, um die Geheimnisse zu erraten, stellt die Mathematik sicher, dass er die echten Übereinstimmungen nicht vom Rauschen unterscheiden kann. Er ist der Wahrheit wirklich blind.
Freunde können sich nicht gegenseitig austricksen: Selbst wenn zwei Freunde zusammenarbeiten, um den dritten auszuspionieren, können sie die Liste des dritten Freundes nicht herausfinden, was die geheimen Masken und die Art und Weise, wie die Photonen rotiert werden, verhindern.

5. Der „Toy Model“-Beweis

Um zu zeigen, dass dies tatsächlich funktioniert, bauten die Autoren eine kleine Simulation unter Verwendung von IBMs Quantencomputer-Simulator (Qiskit).

Sie simulierten 3 Freunde mit kleinen Listen.
Sie fügten „Rauschen“ hinzu (um reale Unvollkommenheiten zu simulieren).
Das Ergebnis: Das System identifizierte korrekt, dass die Freunde 2 Filme gemeinsam hatten (was unter ihrem Schwellenwert von 3 lag). Das System sagte „Nein“, und die Freunde erfuhren nichts.
Sie zeigten dann, dass das System korrekt „Ja“ sagen und die Liste offenlegen würde, wenn sie 3 Übereinstimmungen gehabt hätten.

Zusammenfassung

Dieses Paper führt ein Quantum Multi-Party Threshold PSI-Protokoll ein.

Ziel: Ein gemeinsames Geheimnis enthüllen, aber nur, wenn die Gruppe groß genug ist.
Innovation: Es trennt den Akt des Messens (durchgeführt von einem Schiedsrichter) vom Akt des Interpretierens (durchgeführt von der Gruppe).
Mechanismus: Es verwendet rotierende Photonen und geheime „Flips“, um „verborgene Labels“ zu erzeugen, die der Schiedsrichter nicht lesen kann, wodurch sichergestellt wird, dass die exakte Anzahl der Übereinstimmungen privat bleibt.
Ergebnis: Die Gruppe erfährt nur ein einfaches „Ja/Nein“ über den Schwellenwert, und nur wenn „Ja“ gilt, sehen sie die tatsächlichen gemeinsamen Elemente.

Technische Zusammenfassung: Quantenbasierte Multi-Party Threshold Private Set Intersection mit explizitem Kardinalitätstest

Problemstellung
Private Set Intersection (PSI) ermöglicht es Parteien, die Schnittmenge ihrer privaten Mengen zu berechnen, ohne nicht-überschneidende Elemente preiszugeben. Threshold PSI (TPSI) erweitert dies dadurch, dass die Schnittmenge nur dann offengelegt wird, wenn deren Kardinalität einen öffentlichen Schwellenwert $\tau$ erreicht oder überschreitet. Während klassische TPSI-Protokolle existieren, verlassen sich bestehende Quanten-TPSI-Protokolle (z. B. [MSD+24, LZY+26, WLS+26]) typischerweise auf eine dritte Partei (Third Party, TP), welche die abschließenden Messungen durchführt und die Ergebnisse interpretiert. In diesen Schemata gewinnt die TP die exakte Kardinalität der Schnittmenge zurück und vergleicht diese dann mit $\tau$ . Dieser Ansatz weicht vom idealen TPSI-Paradigma ab, da er die exakte Kardinalitätsstatistik an die TP preisgibt, anstatt nur das Ein-Bit-Prädikat $\mathbb{1}[|\bigcap X_i| \ge \tau]$ zu offenbaren. Dies führt zu einer Funktionslücke und einer Konzentration der Autorität, bei der die TP sowohl als Quantenressourcen-Anbieter als auch als semantischer Interpret der privaten Daten fungiert.

Methodik
Die Autoren schlagen ein Multi-Party Quantum TPSI (MP-QTPSI) Protokoll vor, das die Rolle der Messung von der Rolle der semantischen Interpretation entkoppelt. Das Protokoll umfasst $n$ Teilnehmer ( $P_1, \dots, P_n$ ) und eine semi-ehrliche TP.

Quantenphase (Konstruktion verborgener Labels):
- Setup: Die Teilnehmer etablieren einen Master-Schlüssel über einen TP-freien Quantum Conference Key Agreement (QCKA), um einen positionsversteckten Schlüssel $k$ , einen verborgenen Label-Flip-Vektor $\mathbf{b}$ und Rotationsanteile $\Delta_i$ abzuleiten. Die TP und jeder Teilnehmer etablieren paarweise Schlüssel für Rotationsmasken $T_i$ .
- Kodierung: Die Teilnehmer erweitern ihre Mengen um positive Anker-Mengen und wenden eine positionsversteckte Abbildung $x \mapsto kx \mod M$ an. Sie kodieren ihre Mengen in Indikatorvektoren $Y_i$ .
- Interaktion: Die TP bereitet Einzelphotonen-Sequenzen vor und wendet eine initiale Blinding-Rotation an. Die Sequenzen durchlaufen die Teilnehmer nacheinander. Jeder Teilnehmer $P_i$ wendet eine Rotation basierend auf seinen Daten ($0$ oder $\pi/n$ ), seiner paarweisen Maske $T_i$ und seinem Rotationsanteil $\Delta_i$ an.
- Messung: Die TP entfernt ihre bekannten Masken und misst die Sequenzen. Aufgrund der korrelierten aggregierten Rotationen sind die Messergebnisse nur für Positionen deterministisch, an denen alle Teilnehmer das Element halten (Schnittmenge) oder keines (Nicht-Schnittmenge), aber die semantische Bedeutung dieser Ergebnisse (welches Label der „Schnittmenge“ entspricht) wird durch den verborgenen Flip-Vektor $\mathbf{b}$ verschleiert. Die TP erhält verborgene Label-Indikatorvektoren $z_S$ (gleich) und $z_O$ (entgegengesetzt), kann diese jedoch ohne Informationen von der Teilnehmerseite nicht interpretieren.
Klassische Phase (Kardinalitätstest):
- Maskierter Konsistenztest: Das Protokoll konvertiert die verborgenen Messungen in einen maskierten Label-Konsistenztest. Die Teilnehmer halten Referenz-Labels $\rho$ und Selektor-Masken für reale und Anker-Domänen bereit.
- Oblivious Linear Evaluation (OLE): Die TP und die Teilnehmer nutzen OLE-basierte Oblivious Inner Product (OIP) Berechnungen, um additive Anteile der Konsistenz-Zählungen (Inkonsistenzen $d_{\mathcal{R}}$ und $d_{\mathcal{A}}$ ) zu berechnen, ohne die Vektoren einander preiszugeben.
- Schwellenwertentscheidung: Eine leichtgewichtige Garbled Circuit evaluiert das Prädikat $\text{flag} = 1 \iff (d_{\mathcal{A}} = 0) \land (d_{\mathcal{R}} \le |\mathcal{R}| - \tau)$ . Dies gibt nur das boolesche Ergebnis aus, wodurch sichergestellt wird, dass die exakte Kardinalität niemals an die TP preisgegeben wird.
- Rekonstruktion: Wenn $\text{flag}=1$ , sendet die TP die verborgenen Vektoren aus, und die Teilnehmer nutzen ihre Referenz-Labels und den inversen Schlüssel $k^{-1}$ , um die Schnittmenge zu rekonstruieren.

Wesentliche Beiträge

Expliziter Kardinalitätstest: Das Protokoll ist das erste Quanten-TPSI, das strikt dem Kardinalitätstest-Paradigma folgt, indem es nur das Schwellenwert-Prädikat $\mathbb{1}[|\bigcap X_i| \ge \tau]$ ausgibt, ohne die exakte Kardinalität an die TP zu offenbaren.
Hidden-Label Quanten-Design: Durch die Nutzung von Teilnehmer-seitigen korrelierten aggregierten Rotationen und eines verborgenen Flip-Vektors stellt das Protokoll sicher, dass die Messergebnisse der TP semantisch verschleiert sind. Die TP agiert rein als Messpartei und ist nicht in der Lage, die Ergebnisse bestimmten Mengelementen oder der Kardinalität zuzuordnen.
Sicherheit gegen Kollusion und TP: Das Protokoll beweist Sicherheit gegen externe Lauscher (via Decoy-Photonen), die semi-ehrliche TP (die weder Mengen noch Kardinalität erfährt) und kolludierende Teilnehmer (die die Mengen anderer aufgrund von paarweisen Masken und unbekannten Blinding-Rotationen nicht inferieren können).
Manipulationserkennung: Die Einbeziehung verborgener Anker-Mengen ermöglicht einen Konsistenzcheck ( $d_{\mathcal{A}}=0$ ), der feststellen kann, ob die TP die gemeldeten Messvektoren modifiziert hat.

Ergebnisse

Korrektheit: Theoretische Beweise zeigen, dass das Protokoll das Schnittmenge-Muster korrekt kodiert und dass das klassische Subprotokoll die Schwellenwertbedingung korrekt evaluiert.
Simulation: Die Autoren implementierten die Quantenphase auf der IBM Qiskit-Plattform unter Verwendung eines Toy-Modells ( $n=3$ , Domänengröße 8). Die Simulation beinhaltete Depolarisierungs-, Phasen-Dämpfungs- und Readout-Fehler. Die verrauschten Simulationsergebnisse (Tabelle 3) stimmten eng mit den theoretischen Wahrscheinlichkeiten überein und bestanden erfolgreich den Anker-Check sowie den Schwellenwerttest, um die korrekte Schnittmenge $\{1, 3\}$ zu rekonstruieren.
Komplexität: Die Quantenkommunikationskosten sind $\mathcal{O}(n(\ell M + \delta))$ , und die Berechnungskosten sind ähnlich, wobei $M$ die augmentierte Domänengröße, $\ell$ die Wiederholungszahl und $\delta$ die Anzahl der Decoys ist.

Bedeutung und Ansprüche
Das Paper behauptet, dass seine primäre Bedeutung in der Lösung der „Funktionalitätslücke“ bestehender Quanten-TPSI-Protokolle liegt. Durch die Trennung der Quantenmessrolle von der semantischen Interpretationsrolle entspricht das vorgeschlagene Protokoll der idealen klassischen TPSI-Definition, bei der die Schwellenwertentscheidung ein direktes Prädikat und keine Nachverarbeitung statistischer Werte ist. Die Autoren betonen, dass ihre Konstruktion lediglich auf Einzelphotonen-Rotationen und einem leichtgewichtigen klassischen Post-Processing-Schritt (OLE und Garbled Circuits) basiert und die Komplexität von Quantum Homomorphic Encryption (QHE) vermeidet, die in anderen aktuellen Arbeiten verwendet wird. Sie führen aus, dass dieses Design einen privateren Ansatz für Multi-Party-Settings bietet, in denen die TP die Größe der Schnittmenge nicht erfahren soll. Das Paper schließt mit dem Hinweis, dass das Framework flexibel ist und potenziell auf gewichtete oder verhältnisbasierte Schwellenwerte ausgeweitet werden könnte, derzeit jedoch unter einem semi-ehrlichen TP-Modell operiert.