Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

Probleemstelling

Private Set Intersection (PSI) stelt twee partijen (een zender en een ontvanger) in staat om de doorsnede van hun respectievelijke verzamelingen te berekenen zonder extra informatie prijs te geven. Standaard PSI vereist echter exacte matches. In veel praktische toepassingen, zoals biometrische authenticatie (vingerafdrukken, gezichtsherkenning) of medische data-analyse, zijn exacte matches vaak onmogelijk of onpraktisch vanwege meetfouten of variaties in de data.

Hier komt Fuzzy PSI (FPSI) om de hoek kijken: de ontvanger wil leren welke items $q$ uit de zender's verzameling $Q$ binnen een bepaalde afstand $\delta$ liggen van items $w$ in de ontvanger's verzameling $W$, onder een gegeven metriek (zoals $L_p$-afstand).

Bestaande oplossingen voor FPSI met $L_p$-afstanden (waarbij $p \in [1, \infty]$) hebben twee grote nadelen:

1. Ze vertrouwen zwaar op dure homomorfische encryptie (zoals ElGamal of Paillier), wat leidt tot hoge rekentijd.
2. Ze hebben vaak een exponentiële complexiteit ten opzichte van de dimensie van de data-elementen, wat ze onbruikbaar maakt voor hoogdimensionale datasets.

De kernvraag van dit werk is: Kunnen we concrete, efficiënte FPSI-protocollen bouwen voor algemene $L_p$-afstanden met lineaire complexiteit in de grootte van de verzameling en de dimensie, zonder dure publieke sleutel-operaties?

Methodologie en Kernbijdragen

De auteurs stellen een nieuw, modulair framework voor dat voornamelijk gebruikmaakt van lichtgewicht symmetrische cryptografische operaties in plaats van homomorfische encryptie. De belangrijkste technische bijdragen zijn:

1. Secret-shared Oblivious Programmable PRF (so-OPPRF):
   Dit is de kernbouwblok van het protocol. Een standaard OPPRF laat de ontvanger een PRF-waarde zien. Bij een so-OPPRF krijgen beide partijen echter geheime delen (secret shares) van de output. Dit voorkomt dat de ontvanger direct informatie leert over de zender's data, terwijl de functionaliteit behouden blijft. Het wordt geïmplementeerd door een Oblivious Key-Value Store (OKVS) te combineren met een secret-shared OPRF (so-OPRF).

2. Modulaire Fuzzy Mapping:
   Het protocol verdeelt het probleem in twee fasen:

   • Coarse Mapping (Ruwe mapping): Elk element krijgt een ID toegewezen. Elementen binnen afstand $\delta$ krijgen dezelfde ID. De auteurs gebruiken een modulaire aanpak met so-OPPRF en si-OPRF (OPRF met geheime inputs) om dit te doen zonder dat de ontvanger leert welke dimensies matchen (wat privacy zou lekken bij eerdere methoden).
   • Refined Filtering (Fijne filtering): Voor kandidaat-paren met dezelfde ID wordt een exacte afstandsberekening uitgevoerd om valse positieven te elimineren.

3. Efficiëntie voor $L_p$-afstanden:
   Het protocol werkt voor alle $L_p$-afstanden ($p \in [1, \infty]$). Voor $L_\infty$ wordt een directe vergelijking gebruikt. Voor $L_p$ (zoals $L_1$ en $L_2$) wordt een conversie van booleaanse naar arithmetische shares (B2A) toegepast om de som van de afstanden te berekenen, gevolgd door een privé-intervaltest.

4. Prefix-optimalisatie:
   Voor grote drempelwaarden $\delta$ is de lineaire complexiteit nog steeds te hoog. De auteurs integreren prefix-technieken. In plaats van het hele interval $[q-\delta, q+\delta]$ te programmeren, wordt dit interval gedecomponeerd in $O(\log \delta)$ voorvoegsels (prefixes). Dit verlaagt de communicatie- en rekentijd van lineair ($O(\delta)$) naar logaritmisch ($O(\log \delta)$) ten opzichte van de drempelwaarde.

Resultaten en Prestaties

De auteurs hebben hun protocollen geïmplementeerd in C++ en vergeleken met de state-of-the-art werken van Gao et al. (ASIACRYPT '24) en Dang et al. (CCS '25), die beide afhankelijk zijn van homomorfische encryptie.

• Snelheid: De nieuwe protocollen zijn 12 tot 145 keer sneller in rekentijd dan Gao et al. en 9 tot 80 keer sneller dan Dang et al.
• Communicatie: Er is een reductie in communicatiekosten van 3 tot 8 keer (ten opzichte van Gao et al.) en 5 tot 19 keer (ten opzichte van Dang et al.).
• Schalbaarheid: De prestaties verbeteren bij grotere datasets omdat de overhead van onderliggende protocollen (zoals "silent OT") beter kan worden afgeschreven.
• Prefix-effect: Voor grote $\delta$ (bijv. 1024) reduceert de prefix-versie de communicatie met een factor 11 en de rekentijd met ongeveer de helft ten opzichte van de niet-geoptimaliseerde versie.

Significantie

Dit werk is significant omdat het voor het eerst concreet efficiënte FPSI-protocollen biedt die lineair schalen met zowel de datasetgrootte als de dimensie, zonder afhankelijk te zijn van de zware computatiekosten van homomorfische encryptie.

• Praktische toepasbaarheid: Door het gebruik van symmetrische cryptografie (zoals PRF's en OT) worden de protocollen veel sneller en geschikter voor real-time toepassingen zoals biometrie en privacy-bewuste data-linkage.
• Universeelheid: Het werkt voor een breed scala aan afstandsfuncties ($L_1, L_2, L_\infty$, etc.), wat het flexibel maakt voor diverse data-types.
• Technologische vooruitgang: De introductie van so-OPPRF als een zelfstandig bouwblok biedt nieuwe mogelijkheden voor andere privacy-bewuste protocollen waar gedeelde outputs nodig zijn.

Kortom, dit onderzoek lost een belangrijk knelpunt op in de privacy-bewuste data-analyse door een brug te slaan tussen theoretische haalbaarheid en praktische efficiëntie voor fuzzy matching in hoogdimensionale ruimtes.