💻 computer science

Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

Dieses Paper präsentiert neue Fuzzy Private Set Intersection (FPSI)-Protokolle für allgemeine $L_p$ -Distanzen, die eine optimale logarithmische Abhängigkeit vom Distanzschwellenwert $\delta$ unter Verwendung ausschließlich von Oblivious Transfer und symmetrischen Schlüsselprimitiven erreichen, wodurch die Notwendigkeit teurer homomorpher Verschlüsselung eliminiert wird und gleichzeitig bestehende State-of-the-Art-Lösungen in Bezug auf Laufzeit und Kommunikation signifikant übertroffen wird.

Ursprüngliche Autoren: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Veröffentlicht 2026-06-16

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

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 zwei Personen vor, Alice und Bob, die herausfinden wollen, ob sie „ähnliche“ Gegenstände in ihren jeweiligen Sammlungen haben, ohne sich gegenseitig ihre gesamten Listen zu zeigen.

Das Problem: In einem Standardspiel würden sie nur Gegenstände finden, die exakt identisch sind (z. B. beide haben einen „Roten Apfel“).
Der Twist (Fuzzy PSI): In diesem neuen Spiel wollen sie Gegenstände finden, die „nah genug“ beieinander liegen. Zum Beispiel hat Alice einen „Roten Apfel“ und Bob einen „Leicht angeschlagenen Roten Apfel“ – das soll als Treffer zählen. Die Regel lautet: „Wenn der Unterschied zwischen unseren Gegenständen kleiner als ein bestimmter Abstand (nennen wir ihn den Schwellenwert) ist, gelten sie als Übereinstimmung.“

Die Herausforderung besteht darin, dies sicher zu gestalten. Alice soll nicht Bobs gesamte Liste erfahren, und Bob soll nicht Alices gesamte Liste erfahren. Sie wollen nur wissen, welche Gegenstände „nah genug“ beieinander liegen.

Der alte Weg: Die langsame, teure Suche

Frühere Methoden für dieses „Fuzzy Matching“-Spiel hatten zwei große Probleme:

Die „Lineare Falle“: Wenn der Schwellenwert für die „Nähe“ groß war (sagen wir 100 Einheiten), mussten die Computer für jeden einzelnen Gegenstand 100 verschiedene Möglichkeiten prüfen. Es war, als würde man eine Nadel im Heuhaufen suchen, indem man jedes einzelne Halm nach dem anderen prüft. Je größer der Schwellenwert, desto langsamer wurde es.
Das „Schwerer Maschinenwerkzeug“-Problem: Um dies sicher zu machen, nutzten alte Methoden sehr schwere, langsame kryptografische Werkzeuge (wie additive homomorphe Verschlüsselung). Stellen Sie sich das so vor, als würde man versuchen, eine geheime Nachricht mit einem massiven, treibstofffressenden LKW zu versenden, obwohl ein Fahrrad völlig ausreichen würde.

Der neue Durchbruch: Die „Präfix“-Abkürzung

Dieses Paper stellt eine neue Art vor, das Spiel zu spielen, die schnell, leichtgewichtig und intelligent ist.

1. Die „Postleitzahl“-Analogie (Präfixe)

Anstatt jeden Zahlenbereich einzeln zu prüfen (wie das Prüfen von 10, 11, 12... bis hin zu 100), nutzt der Autor einen Trick namens Präfixe.

Stellen Sie sich vor, Sie suchen ein Haus in einer Stadt.

Der alte Weg: Sie klopfen an jede Tür in der Nachbarschaft, um zu sehen, ob der Bewohner Ihr Freund ist.
Der neue Weg: Sie schauen auf die Postleitzahl. Wenn Ihr Freund in „10001“ wohnt, müssen Sie nur Häuser mit diesem Präfix überprüfen. Sie müssen nicht die ganze Stadt absuchen.

Die Autoren haben erkannt, dass jeder „Bereich“ von Zahlen (der Schwellenwert) in nur wenige „Postleitzahlen“ (Präfixe) zerlegt werden kann.

Die Magie: Die Zeit, die benötigt wird, um diese Präfixe zu prüfen, wächst nicht mit der Größe des Schwellenwerts, sondern logarithmisch.
- Wenn sich der Schwellenwert verdoppelt, steigt der Arbeitsaufwand nur minimal an.
- Wenn der Schwellenwert 100-mal größer wird, verdoppelt sich die Arbeit nur.
- Analogie: Es ist wie das Finden eines Buches in einer Bibliothek. Jedes Buch einzeln zu prüfen dauert ewig. Das Etikett im Regal (das Präfix) zu prüfen, dauert Sekunden, egal wie viele Bücher im Regal stehen.

2. Die „Leichtgewichtigen“ Werkzeuge (Symmetrische Primitive)

Die Autoren haben die schweren „LKWs“ (teure Verschlüsselung) durch „Fahrräder“ (symmetrische Schlüssel-Primitive und Oblivious Transfer) ersetzt.

Oblivious Transfer (OT): Stellen Sie sich einen Kellner vor, der Ihnen eines von zwei geheimen Menü-Elementen geben kann, ohne dass er weiß, welches Sie gewählt haben, und ohne dass Sie wissen, was er über Ihre Wahl weiß. Die Autoren nutzen dies, um Informationen sicher auszutauschen, ohne die gesamte Liste preiszugeben.
Das Ergebnis: Ihr System basiert vollständig auf diesen leichtgewichtigen, schnellen Werkzeugen.

Die zwei Szenarien: Kleine Räume vs. Riesige Hallen

Szenario A: Niedrige Dimensionen (Die „Wohnung“-Annahme)

Das Setting: Denken Sie an einen kleinen Raum, in dem die Menschen weit voneinander entfernt stehen (mindestens 2x der Schwellenwert).
Die Strategie: Sie verwenden Spatial Hashing. Stellen Sie sich vor, der Raum wird in ein Gitternetz aus Kacheln unterteilt. Wenn zwei Personen nah beieinander liegen, müssen sie sich in derscher Kachel oder in benachbarten Kacheln befinden. Das Protokoll prüft nur diese spezifischen Kacheln.
Die Innovation: Sie haben dieses Gittersystem mit dem neuen „Präfix“-Shortcut und einem speziellen „Gleichheitsprüfungs“-Werkzeug (genannt ECSS) kombert. Dies ermöglicht es ihnen, Übereinstimmungen sofort zu finden, ohne jedes Paar einzeln prüfen zu müssen.

Szeno B: Hohe Dimensionen (Die „Lagerhaus“-Annahme)

Das Setting: Denken Sie an ein riesiges, mehrdimensionales Lagerhaus. In hohen Dimensionen erzeugt das Aufteilen des Raums in ein Gitternetz zu viele leere Kacheln (der „Fluch der Dimensionalität“).
Die Strategie: Sie verwenden Distributed ID Generation. Anstatt eines Gitters geben sie jedem Gegenstand eine eindeutige „ID-Karte“ basierend auf seinem Standort.
Die Innovation: Sie haben einen neuen Weg entwickelt, um diese IDs sicher mithilfe ihres „Präfix“-Tricks zu generieren. Selbst in einem riesigen Lagerhaus können sie diese IDs so generieren, dass sie übereinstimmen, falls zwei Gegenstände nah beieinander liegen, ohne die tatsächlichen Standorte der Gegenstände zu verraten.

Das „Geheimrezept“: Equality Conditional Sum

Das Herzstück ihrer Erfindung ist ein neues mathematisches Werkzeug namens Equality Conditional Sum (ECSS).

Wie es funktioniert: Stellen Sie sich vor, Alice und Bob haben beide eine Liste von Zahlen. Sie möchten die Zahlen addieren, aber nur, wenn eine bestimmte Bedingung erfüllt ist (z. B. „Nur addieren, wenn die Präfixe übereinstimmen“).
Die Magie: Sie können diese Addition sicher durchführen, ohne dass eine Partei ihre Zahlen preisgibt. Wenn die Präfixe nicht übereinstimmen, ist das Ergebnis nur zufälliges Rauschen. Wenn sie jedoch übereinstimmen, ist das Ergebnis die korrekte Summe. Dies ermöglicht es ihnen, die Nähe von Gegenständen zu verifizieren, ohne jemals die tatsächlichen Werte zu sehen.

Die Ergebnisse: Eine massive Beschleunigung

Die Autoren haben eine funktionierende Version ihres Systems gebaut und es gegen die besten bestehenden Methoden getestet.

Geschwindigkeit: Ihr System ist bis zu 43,7-mal schneller als die bisher besten Methoden.
Datenverbrauch: Es nutzt bis zu 31,3-mal weniger Daten für den Netzwerktransfer.
Skalierbarkeit: Während andere Systeme abstürzten (aus dem Speicher lief), wenn die Datensätze sehr groß wurden, lief ihr System weiterhin reibungslos.

Zusammenfassung

Kurz gesagt löst dieses Paper das Problem des „Fuzzy Matching“, indem es:

Langsame, schwere Verschlüsselung durch schnelle, leichtgewichtige Werkzeuge ersetzt.
„Präfixe“ (wie Postleitzahlen) verwendet, um eine langsame, lineare Suche in eine schnelle, logarithmische Suche zu verwandeln.
Neue „Geheime Summen“-Werkzeuge entwickelt, die es zwei Parteien ermöglichen, die Nähe zu prüfen, ohne ihre Geheimnisse zu verraten.

Das Ergebnis ist ein System, das in der Lage ist, „ähnliche“ Gegenstände in massiven, privaten Datensätzen fast augenblicklich zu finden, was datenschutzfreundliches Abgleichen in großem Maßstab erst praktikabel macht.

Technische Zusammenfassung: Fuzzy PSI aus symmetrischen Primitiven mit exakter logarithmischer Abhängigkeit vom Distanzschwellenwert

Problemstellung
Fuzzy Private Set Intersection (FPSI) ermöglicht es einem Sender mit einem Satz von $d$ -dimensionalen Vektoren $Q$ und einem Empfänger mit einem Satz $W$ , Elemente $q \in Q$ zu identifizieren, für die gilt, dass es ein $w \in W$ gibt, sodass $\text{dist}(q, w) \le \delta$ , ohne zusätzliche Informationen preiszugeben. Während der Standard-PSI eine hohe Effizienz erreicht hat, stehen bestehende FPSI-Protokolle vor erheblichen theoretischen und praktischen Engpässen. Vorangegangene Arbeiten weisen typischerweise eine lineare Skalierung mit dem Distanzschwellenwert $\delta$ auf (d. h. $O(\delta)$ ), oder erreichen nur eine polylogarithmische Abhängigkeit für $L_\infty$ -Distanzen. Protokolle, die allgemeine Minkowski-Distanzen ( $L_p$ für $p \in [1, \infty]$ ) unterstützen und eine logarithmische Abhängigkeit von $\delta$ aufweisen, haben entweder auf teure additive homomorphe Verschlüsselung (AHE) zurückgegriffen oder litten unter Sicherheitsmängeln und exponentiellen Komplexitätstermen in der Dimension $d$ . Das Ziel ist es, eine exakte logarithmische Abhängigkeit von $\delta$ für allgemeine $L_p$ -Distanzen unter Verwendung ausschließlich effizienter symmetrischer Schlüssel-Primitive zu erreichen.

Methodik und Kerntechniken
Die Autoren schlagen neue FPSI-Protokolle vor, die vollständig auf Oblivious Transfer (OT) und symmetrischen Schlüssel-Primitiven basieren und somit öffentliche Schlüsseloperationen wie AHE vermeiden. Die Konstruktion stützt sich auf zwei primäre Annahmen: die apart-Annahme (geeignet für niedrigdimensionale Settings) und die separate-Annahme (geeignet für hochdimensionale Settings).

Präfix-Repräsentation und Intervallprüfung:
Die Kerninnovation ersetzt die Enumeration aller Ganzzahlen in einem Intervall $[q_k - \delta, q_k + \delta]$ (was $O(\delta)$ kostet) durch eine Präfix-Repräsentation unter Verwendung von $O(\log \delta)$ Präfixen. Dies reduziert die Kosten der Intervallprüfung auf $O(\log \delta)$ pro Dimension.
Equality Conditional Sum/Inner-Product Share (ECSS/ECIPS):
Um die durch das Präfix-Matching erforderliche Interaktion zu handhaben, ohne den Input des Senders preiszugeben oder einen exponentiellen Overhead zu verursachen, führen die Autoren zwei neue kryptographische Primitive ein:
- Equality Conditional Sum Share (ECSS): Wird für die $L_\infty$ -Distanz verwendet. Es ermöglicht den Parteien, eine Summe von Werten bedingt auf einem Gleichheits-Match zwischen Input-Vektoren zu berechnen und Secret Shares des Ergebnisses auszugeben.
- Equality Conditional Inner-Product Share (ECIPS): Wird für allgemeine $L_p$ -Distanzen verwendet. Es berechnet ein Skalarprodukt bedingt auf Gleichheit, was die Berechnung von $|w_k - q_k|^p$ via Binomialentwicklung ermöglicht, ohne die spezifischen Terme preiszugeben.
  Beide Primitive werden effizient unter Verwendung von OT, Oblivious Programmable PRFs (OPPRF) und Permute+Share (PS) implementiert.
Handhabung mehrerer Elemente:
- Niedrigdimensional ( $L_\infty$ und $L_p$ ): Die Protokolle nutzen Spatial Hashing (Grid Cells) komb in Verbindung mit Cuckoo Hashing, um die Anzahl der paarweisen Vergleiche zu reduzieren. Die Autoren führen Optimierungen mittels Shared OPRF (sOPRF) ein, um die Notwendigkeit von Dummy-Werten in leeren Bins zu eliminieren, wodurch die Positionierung des Hashings des Senders verborgen bleibt und die Notwendigkeit globaler Permutationsschritte in bestimmten Konfigurationen entfällt.
- Hochdimensional ( $L_\infty$ und $L_p$ ): Um die exponentielle $O(2^d)$ -Kosten von Spatial Hashing zu vermeiden, verwenden die Autoren ein Distributed ID Generation (dIDG) Protokoll. Dieses Protokoll generiert eindeutige IDs für Elemente, sodass nahe beieinander liegende Elemente eine gemeinsame ID teilen. Die Autoren identifizieren Sicherheitslücken in vorangegangenen dIDG-Konstruktionen (speziell in [DZL25]), die mit Kollisions-Leakage zusammenhängen, und schlagen ein sicheres, auf symmetrischen Schlüsseln basierendes dIDG unter Verwendung von sOPRF und ECSS vor.

Kernbeiträge

Neue Primitive: Die Einführung von ECSS und ECIPS, die effizientes Fuzzy-Matching mit exakter logarithmischer Abhängigkeit von $\delta$ unter Verwendung ausschließlich symmetrischer Primitive ermöglichen.
Optimale Komplexität: Die ersten FPSI-Protokolle für allgemeine $L_p \in [1, \infty]$ Distanzen, die eine strikt logarithmische Komplexität $O(d \log \delta)$ in Bezug auf den Schwellenwert $\delta$ erreichen. Dies ist theoretisch optimal, da das Unterscheiden von Werten in einem Intervall der Länge $O(\delta)$ $\Omega(\log \delta)$ Bits an Information erfordert.
Sicherheit und Effizienz: Die Protokolle eliminieren die Abhängigkeit von AHE und ersetzen diese durch OT und symmetrische Schlüssel-Operationen. Die Autoren identifizieren zudem Sicherheitslücken in aktuellen präfixbasierten Protokollen (z. B. [DZL25]), die unter Masken-Wiederverwendung und Kollisions-Leakage litten.
Skalierbare Konstruktionen: Getrennte Konstruktionen für niedrigdimensionale (unter Verwendung von Spatial Hashing) und hochdimensionale (unter Verwendung von dIDG) Settings, die jeweils eine optimale asymptotische Komplexität erreichen.

Experimentelle Ergebnisse
Die Autoren haben ihre Protokolle implementiert und mit dem aktuellen Stand der Technik ([GQL+24], [DZL25], [BGMP25]) verglichen.

Performance: Die neuen Protokolle übertreffen den Stand der Technik signifikant. In niedrigdimensionalen Settings erreichen sie eine bis zu 43,7-mal schnellere Laufzeit und einen 31,3-mal geringeren Kommunikations-Overhead.
Skalierbarkeit: Während vorangegangene Arbeiten wie [GQL+24] und [DZL25] in hochdimensionalen Settings bei Set-Größen von $2^{16}$ auf Speicherüberläufe stießen, konnten die vorgeschlagenen Protokolle unter denselben Konfigurationen erfolgreich ausgeführt werden.
Schwellenwert-Abhängigkeit: Die Experimente bestätigen, dass die Laufzeit- und Kommunikationskosten logarithmisch mit $\delta$ skalieren, im Gegensatz zur linearen Skalierung, die bei früheren Protokollen mit linearer Abhängigkeit beobachtet wurde.

Bedeutung
Das Paper beansprucht einen theoretischen Durchbruch in der optimalen Schwellenwert-Skalierung für FPSI und zeigt, dass eine exakte logarithmische Abhängigkeit von $\delta$ für allgemeine $L_p$ -Distanzen ohne kostspielige Public-Key-Kryptographie realisierbar ist. Praktisch gesehen trägt dies zur Machbarkeit skalierbarer FPSI-Anwendungen in Bereichen bei, die Fuzzy-Matching erfordern, wie etwa dem Abgleich genomischer Sequenzen, der Ähnlichkeitssuche bei Bildern oder der Detektion kompromittierter Anmeldedaten, indem die Effizienzengpässe im Zusammenhang mit dem Distanzschwellenwert und der Dimensionalität beseitigt werden.