💻 computer science

Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

Diese Arbeit stellt effiziente Protokolle für fuzzy private set intersection (FPSI) vor, die auf geheimgeteilten OPRFs und symmetrischen Verschlüsselungen basieren, lineare Komplexität aufweisen und im Vergleich zu aktuellen State-of-the-Art-Lösungen signifikant schnellere Laufzeiten sowie geringere Kommunikationskosten bieten.

Ursprüngliche Autoren: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

Veröffentlicht 2026-04-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Xinpeng Yang, Meng Hao, Chenkai Weng, Robert H. Deng, Yonggang Wen, Tianwei Zhang

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

Die große Geschichte: Das „Fast-Genau"-Treffen

Stellen Sie sich vor, Sie haben zwei riesige Listen von Menschen.

Liste A (Der Absender) hat eine Liste von 1 Million Gesichtsdaten (z. B. von Mitarbeitern).
Liste B (Der Empfänger) hat eine Liste von 1 Million Gesichtsdaten (z. B. von Besuchern an der Tür).

Das Ziel: Der Empfänger möchte herausfinden, welche Besucher auch auf der Mitarbeiterliste stehen.

Das Problem: In der echten Welt sind Gesichter nie exakt gleich. Ein Foto am Morgen sieht anders aus als eines am Abend. Eine Brille, eine andere Frisur oder ein leichtes Lächeln verändern die Daten. Ein herkömmliches Computersystem würde sagen: „Das ist nicht derselbe Mensch, weil die Zahlen nicht zu 100 % übereinstimmen." Das ist für Sicherheitschecks unbrauchbar.

Die Lösung (Fuzzy PSI): Wir brauchen ein System, das sagt: „Das ist fast derselbe Mensch, die Gesichter sind sich ähnlich genug." Aber hier kommt das große „Aber": Niemand darf die ganze Liste der anderen sehen. Der Empfänger darf nur wissen, welche Besucher auf der Liste stehen, aber nicht, wer sonst noch auf der Liste ist. Und der Absender darf nicht wissen, welche Besucher gerade an der Tür waren.

Das alte Problem: Der langsame, teure Wächter

Bisher gab es Methoden, um dieses „Fast-Genau"-Vergleichen sicher durchzuführen. Aber diese Methoden waren wie ein sehr langsamer, alter Wächter, der jede einzelne Zahl auf beiden Listen mit einem Taschenrechner durchrechnen musste.

Sie waren extrem teuer (benötigten viel Rechenzeit).
Sie waren langsam (wie ein Schneckenrennen bei großen Datenmengen).
Sie nutzten komplexe mathematische Werkzeuge (wie „homomorphe Verschlüsselung"), die man sich wie das Öffnen eines Safe mit einem Hammer vorstellen kann – sicher, aber ineffizient.

Die neue Erfindung: Der clevere Schlüsselmechanismus

Die Autoren dieses Papiers haben einen neuen, viel schnelleren Weg gefunden. Sie nutzen keine schweren mathematischen Hammer, sondern leichte, schnelle Werkzeuge (symmetrische Verschlüsselung), die wie ein gut geölter Türschloss-Mechanismus funktionieren.

Hier sind die drei genialen Tricks, die sie benutzt haben:

1. Der „Geheimnis-Teiler" (so-OPPRF)

Stellen Sie sich vor, Sie wollen ein geheimes Wort (z. B. einen Code) an jemanden weitergeben, ohne dass dieser das Wort direkt sieht.

Der alte Weg: Der Absender gibt das Wort in einen Safe, der Empfänger muss den Safe knacken.
Der neue Weg: Der Absender und der Empfänger teilen sich das Wort in zwei Hälften. Jeder hat nur ein Stück. Zusammen ergeben sie das Wort, aber einzeln ist es nur ein Haufen Kauderwelsch.
Warum ist das toll? Das ist viel schneller zu berechnen als ein Safe-Knacken. Es erlaubt den Computern, zu prüfen: „Haben wir zusammen das richtige Wort?", ohne dass einer von beiden das Wort allein kennt.

2. Die „Zonen-Markierung" (Fuzzy Mapping)

Wie findet man heraus, ob zwei Gesichter ähnlich sind, ohne sie direkt zu vergleichen?
Stellen Sie sich vor, die Welt ist in viele kleine Zonen unterteilt.

Wenn ein Gesicht in Zone A liegt, bekommt es ein Ticket mit der Aufschrift „Zone A".
Wenn ein anderes Gesicht fast in Zone A liegt (aber vielleicht ein bisschen daneben), bekommt es auch ein Ticket „Zone A".
Der Trick: Die Autoren haben eine Methode entwickelt, um diese Zonen so zu markieren, dass alle ähnlichen Gesichter das gleiche Ticket bekommen, ohne dass jemand weiß, welche Gesichter genau in welche Zone fallen. Sie nutzen dabei die „Geheimnis-Teiler"-Methode, um die Tickets sicher zu verteilen.

3. Der „Vorwort"-Trick (Prefix Optimization)

Was passiert, wenn die Zone sehr groß ist? (z. B. wenn wir Gesichter vergleichen, die sehr unterschiedlich aussehen dürfen).

Ohne Trick: Man müsste alle 1000 Punkte in der Zone prüfen. Das dauert ewig.
Mit dem Trick: Man nutzt „Vorwörter". Statt jeden Punkt zu prüfen, prüft man nur die ersten paar Buchstaben des Namens. Wenn die ersten 3 Buchstaben übereinstimmen, ist es wahrscheinlich derselbe Bereich.
Das Ergebnis: Statt 1000 Schritte braucht man nur noch 10 Schritte. Das macht das System bei großen Toleranzen (wenn „ähnlich" sehr weit gefasst ist) unglaublich schnell.

Das Ergebnis: Ein Blitz im Vergleich zu einem Schneckentempo

Die Autoren haben ihre neue Methode getestet und mit den besten bisherigen Methoden verglichen. Das Ergebnis ist beeindruckend:

Geschwindigkeit: Ihr System ist bis zu 145-mal schneller. Stellen Sie sich vor, ein Vorgang, der früher einen ganzen Tag dauerte, dauert jetzt nur noch wenige Minuten.
Datenmenge: Sie müssen viel weniger Daten über das Internet senden (bis zu 19-mal weniger). Das ist wie der Unterschied zwischen dem Versand eines ganzen LKWs voller Papier und einer einzigen E-Mail.

Warum ist das wichtig?

Diese Technologie ist wie ein unsichtbarer, super-schneller Türsteher für die digitale Welt.

Medizin: Krankenhäuser können Patientenlisten vergleichen, um doppelte Einträge zu finden, ohne die Namen der Patienten preiszugeben.
Sicherheit: Banken können betrügerische Konten finden, die leicht verändert wurden, ohne die echten Konten der Kunden zu offenbaren.
Biometrie: Ihr Smartphone kann Ihr Gesicht erkennen, auch wenn Sie eine Sonnenbrille tragen, ohne dass die Daten Ihres Gesichts auf einen Server hochgeladen werden, wo sie gestohlen werden könnten.

Zusammenfassend: Die Autoren haben einen Weg gefunden, „ähnliche" Dinge sicher und blitzschnell zu vergleichen, ohne dass die Geheimnisse der Listen verraten werden. Sie haben den schweren, langsamen Hammer gegen einen leichten, schnellen Schlüsselmechanismus getauscht.

1. Problemstellung

Das Private Set Intersection (PSI)-Problem ermöglicht es zwei Parteien (Sender und Empfänger), den Schnitt ihrer jeweiligen Mengen zu berechnen, ohne weitere Informationen über die nicht-schnittmengen-Elemente preiszugeben. Herkömmliche PSI-Protokolle basieren auf exaktem Matching.

In vielen realen Anwendungen, wie z. B. biometrischer Authentifizierung (Fingerabdruck, Gesichtserkennung) oder medizinischen Datenanalysen, sind exakte Übereinstimmungen jedoch oft unmöglich oder unpraktisch, da Daten durch Rauschen oder Umgebungsvariationen leicht variieren. Hier kommt das Fuzzy Private Set Intersection (FPSI) ins Spiel. Beim FPSI möchte der Empfänger herausfinden, welche Elemente $q$ aus der Sender-Menge $Q$ eine Distanz $\le \delta$ zu mindestens einem Element $w$ in der Empfänger-Menge $W$ haben (unter einer Metrik $L_p$ , wobei $p \in [1, \infty]$ ).

Herausforderungen bestehender Lösungen:
Bisherige Ansätze für FPSI mit $L_p$ -Metriken leiden unter erheblichen Ineffizienzen:

Sie basieren oft auf teuren homomorphen Verschlüsselungen (z. B. ElGamal, Paillier), was zu hohen Rechenkosten führt.
Viele Protokolle weisen eine exponentielle Komplexität bezüglich der Elementdimension $d$ auf.
Neuere lineare Ansätze (z. B. von Gao et al. oder Dang et al.) reduzieren zwar die Komplexität, bleiben aber stark von homomorphen Verschlüsselungen abhängig, was die praktische Effizienz einschränkt.

2. Methodik und Kernkonzepte

Die Autoren schlagen einen neuen Ansatz vor, der primär auf effizienten symmetrischen Krypto-Primitiven basiert und eine lineare Komplexität bezüglich der Mengengrößen ( $m, n$ ), der Dimension ( $d$ ) und des Distanzschwellenwerts ( $\delta$ ) erreicht.

A. Secret-shared Oblivious Programmable PRF (so-OPPRF)

Das zentrale Baustein-Element ist eine neue Variante des Oblivious Programmable Pseudorandom Function (OPPRF), genannt so-OPPRF.

Funktionsweise: Im Gegensatz zu einem Standard-OPPRF, bei dem der Empfänger den PRF-Wert erhält, erhalten bei so-OPPRF beide Parteien Geheimnisse (Secret Shares) des Ausgabewerts. Der Sender erhält $f^S$ und der Empfänger $f^R$ , sodass $f^S + f^R = \text{PRF}(k, x)$ gilt.
Implementierung: Dies wird durch die Kombination eines Oblivious Key-Value Store (OKVS) mit einem Secret-shared OPRF (so-OPRF) realisiert. Der Sender kodiert die Programmierpunkte (Input-Output-Paare) mittels OKVS und sendet die Kodierung an den Empfänger. Zusammen mit den Shares aus dem so-OPRF können beide Parteien die korrekten Shares für beliebige Inputs berechnen, ohne dass einer der Parteien den vollständigen Wert allein kennt.

B. Modulares Fuzzy-Mapping

Das FPSI-Protokoll folgt einem Zwei-Phasen-Paradigma:

Coarse Mapping (Grobe Zuordnung): Elemente, die innerhalb der Distanz $\delta$ $δ$ liegen, erhalten dieselbe Identifikations-ID. Dies wird durch eine modulare Konstruktion erreicht, die lokale Abbildungen (basierend auf Intervallen um die Datenpunkte) und eine globale PRF-basierte Kombination nutzt.
- Um Informationslecks zu vermeiden (z. B. wenn der Empfänger durch gleiche PRF-Ausgaben auf Intervallüberlappungen schließen könnte), nutzen die Autoren si-OPRF (Secret-shared Input OPRF). Dabei sind sowohl der Schlüssel als auch der Input zwischen den Parteien geteilt, was eine sichere Kombination der lokalen IDs ermöglicht, ohne die Rohdaten preiszugeben.
Refined Filtering (Verfeinerte Filterung): Nach der groben Zuordnung werden potenzielle Kandidatenpaare (gleiche IDs) auf ihre tatsächliche Distanz geprüft.
- Für $L_\infty$ : Ein einfacher Private Equality Test (PEQT) prüft, ob die Summe der Secret Shares null ist (was bedeutet, dass alle Dimensionen innerhalb $\delta$ liegen).
- Für $L_p$ ( $p < \infty$ ): Es wird eine Umwandlung von booleschen zu arithmetischen Shares (B2A) benötigt, um die $p$ -te Potenz der Distanz zu berechnen, gefolgt von einem Private Interval Test.

C. Prefix-Optimierung

Für große Schwellenwerte $\delta$ wird die lineare Abhängigkeit von $\delta$ (Komplexität $O(\delta)$ ) durch die Verwendung von Prefix-Techniken auf logarithmische Komplexität ( $O(\log \delta)$ ) reduziert.

Statt das gesamte Intervall $[q - \delta, q + \delta]$ zu programmieren, wird dieses Intervall in eine kleine Menge von Präfixen zerlegt, die das Intervall abdecken.
Dies reduziert die Anzahl der zu verarbeitenden Schlüssel-Wert-Paare erheblich, was bei großen $\delta$ entscheidend ist.

3. Schlüsselbeiträge

Einführung von so-OPPRF: Ein neues primitives Bauteil, das die Ausgabe von OPPRF als Secret Shares bereitstellt, was die Basis für effiziente, nicht-leckende fuzzy-Mapping-Protokolle bildet.
Modulares Design: Eine klare Trennung von Fuzzy-Mapping und Fuzzy-Matching, die die Implementierung und Analyse vereinfacht.
Effiziente Protokolle für $L_p$ -Metriken: Die ersten Protokolle für allgemeine $L_p$ -Metriken ( $p \in [1, \infty]$ ), die eine lineare Komplexität in allen Parametern ( $m, n, d, \delta$ ) erreichen und dabei auf teure Public-Key-Operationen verzichten.
Prefix-Optimierung: Eine Anpassung der Protokolle für große $\delta$ , die die Komplexität von linear auf logarithmisch in Bezug auf $\delta$ senkt.
Umfassende Evaluierung: Experimenteller Nachweis der Überlegenheit gegenüber dem aktuellen Stand der Technik (State-of-the-Art).

4. Ergebnisse

Die Autoren haben ihre Protokolle in C++ implementiert und mit den besten bisherigen linearen Ansätzen (Gao et al., ASIACRYPT'24 und Dang et al., CCS'25) verglichen.

Laufzeit: Die Protokolle sind 12- bis 145-mal schneller als Gao et al. und 9- bis 80-mal schneller als Dang et al.
Kommunikationskosten: Die Kommunikationskosten wurden um den Faktor 3- bis 8-mal (gegenüber Gao) bzw. 5- bis 19-mal (gegenüber Dang) reduziert.
Skalierbarkeit: Die Vorteile sind besonders bei großen Eingabemengen ( $m=n=2^{16}$ ) und hohen Dimensionen ( $d=16$ ) ausgeprägt.
Prefix-Effizienz: Bei großen Schwellenwerten ( $\delta \ge 64$ ) übertrifft die prefix-optimierte Version die nicht-optimierte Version deutlich in der Kommunikation (bis zu 11-fache Reduktion bei $\delta=1024$ ).

5. Bedeutung und Fazit

Diese Arbeit stellt einen bedeutenden Fortschritt im Bereich der sicheren Mehrparteienberechnung (MPC) dar, insbesondere für datenschutzkonforme Anwendungen mit unscharfen Daten (z. B. Biometrie).

Praktische Anwendbarkeit: Durch den Verzicht auf homomorphe Verschlüsselung und die Nutzung symmetrischer Primitiven (die deutlich schneller sind) werden FPSI-Protokolle erstmals für reale, hochdimensionale Anwendungen praktikabel.
Theoretischer Durchbruch: Die Einführung von so-OPPRF und die modulare Konstruktion bieten neue Wege, um komplexe fuzzy-Logik in MPC sicher und effizient zu integrieren.
Zukunftsaussichten: Obwohl das Protokoll unter semi-honnesten Annahmen sicher ist und bestimmte Verteilungsannahmen (disjoint projection) voraussetzt, legt es den Grundstein für zukünftige Arbeiten, die diese Annahmen lockern oder die Sicherheit gegen böswillige Angreifer (malicious security) ohne massive Effizienzverluste erreichen sollen.

Zusammenfassend bietet das Paper eine konkret effiziente Lösung für das Fuzzy-PSI-Problem, die sowohl in der Rechengeschwindigkeit als auch im Kommunikationsaufwand den aktuellen State-of-the-Art deutlich hinter sich lässt.