💻 computer science

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

Dit artikel presenteert nieuwe Fuzzy Private Set Intersection (FPSI) protocollen voor algemene $L_p$ -afstanden die een optimale logaritmische afhankelijkheid van de afstandsdrempel $\delta$ bereiken met behulp van enkel oblivious transfer en symmetrische-sleutel primitieven, waardoor de noodzaak voor dure homomorfe encryptie wordt geëlimineerd terwijl ze de huidige state-of-the-art oplossingen aanzienlijk overtreft in runtime en communicatie.

Oorspronkelijke auteurs: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Gepubliceerd 2026-06-16

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Cong Zhang, Yang Cao, Yujie Bai, Shuaishuai Li, Juntong Lin, Yu Chen, Anyu Wang, Xiaoyun Wang

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je twee mensen voor, Alice en Bob, die willen uitzoeken of ze "vergelijkbare" items hebben in hun respectievelijke collecties zonder hun volledige lijsten aan elkaar te laten zien.

Het Probleem: In een standaardspel zouden ze alleen items matchen die exact hetzelfde zijn (bijv. beiden hebben een "Rode Appel").
De Twist (Fuzzy PSI): In dit nieuwe spel willen ze items matchen die dicht genoeg bij elkaar liggen. Bijvoorbeeld, als Alice een "Rode Appel" heeft en Bob een "Iets geplette Rode Appel", dan tellen ze als een match. De regel is: "Als het verschil tussen onze items kleiner is dan een specifieke afstand (laten we dat de Drempelwaarde noemen), dan matchen we."

De uitdaging is om dit veilig te doen. Alice mag de volledige lijst van Bob niet leren, en Bob mag de volledige lijst van Alice niet leren. Ze willen alleen weten welke items dicht genoeg bij elkaar liggen.

De Oude Manier: De Trage, Dure Zoektocht

Eerdere methoden voor dit "Fuzzy Matching"-spel hadden twee grote problemen:

De "Lineaire" Valstrik: Als de "nabijheid"-drempelwaarde groot was (bijv. 100 eenheden), moesten de computers 100 verschillende mogelijkheden controleren voor elk item. Het was alsof je een naald in een hooiberg zocht door elke strohalm één voor één te controleren. Hoe groter de drempelwaarde, hoe trager het werd.
Het "Zware Machinepark" Probleem: Om dit veilig te laten werken, gebruikten oude methoden zeer zware, trage cryptografische tools (zoals Additive Homomorphic Encryption). Denk aan het proberen te versturen van een geheim bericht met een enorme, brandstofverslindende vrachtwagen wanneer een fiets ook zou volstaan.

De Nieuwe Doorbraak: De "Prefix" Afkorting

Dit paper introduceert een nieuwe manier om het spel te spelen die snel, lichtgewicht en slim is.

1. De "Postcode" Analogie (Prefixes)

In plaats van elke mogelijke waarde in een bereik te controleren (zoals controleren of een getal 10, 11, 12... tot en met 100 is), gebruikt de auteur een truc genaamd Prefixes.

Stel je voor dat je op zoek bent naar een huis in een stad.

Oude Manier: Je klopt bij elke deur in de buurt aan om te zien of de bewoner je vriend is.
Nieuwe Manier: Je kijkt naar de Postcode. Als je vriend in "10001" woont, hoef je alleen maar huizen met die prefix te controlen. Je hoeft niet de hele stad te controleren.

De auteurs realiseerden zich dat elk "bereik" van getallen (de drempelwaarde) kan worden opgedeeld in slechts een paar "Postcodes" (prefixes).

De Magie: De tijd die het kost om deze prefixes te controleren groeit niet mee met de grootte van de drempelwaarde, maar groeit logaritmisch.
- Als de drempelwaarde verdubbelt, is de extra inspanning slechts een klein beetje.
- Als de drempelwaarde 100 keer groter wordt, verdubbelt de hoeveelheid werk slechts.
- Analogie: Het is als het zoeken van een boek in een bibliotheek. Elk boek afzonderlijk controleren duurt eeuwig. Het controleren van het etiket op de plank (de prefix) kost seconden, ongeacht hoeveel boeken er op de plank staan.

2. De "Lichtgewicht" Tools (Symmetric Primitives)

De auteurs hebben de zware "vrachtwagens" (dure encryptie) vervangen door "fietsen" (symmetrische sleutel-primitieven en Oblivious Transfer).

Oblivious Transfer (OT): Stel je een ober voor die je één van de twee geheime menukaarten kan geven zonder dat hij weet welke je hebt gekozen, en zonder dat jij weet welke de andere optie was. De auteurs gebruiken dit om informatie veilig uit te wisselen zonder de volledige lijst te onthullen.
Het Resultaat: Hun systeem is volledig gebouwd van deze lichtgewicht, snelle tools.

De Twee Scenario's: Kleine Kamers versus Gigantische Hallen

Het paper biedt twee verschillende strategieën aan, afhankelijk van hoe "druk" de data is (dimensionaliteit):

Scenario A: Lage Dimensies (De "Appartement" Aanname)

De Setting: Denk aan een kleine kamer waar mensen ver van elkaar staan (ten minste 2x de drempelwaarde afstand).
De Strategie: Ze gebruiken Spatial Hashing. Stel je voor dat je een kamer verdeelt in een raster van tegels. Als twee mensen dicht bij elkaar staan, moeten ze in dezelfde tegel of in naburige tegels staan. Het protocol controleert alleen die specifieke tegels.
De Innovatie: Ze hebben dit rastersysteem gecombineerd met hun nieuwe "Prefix"-afkorting en een speciale "Gelijkheid Check" tool (genoemd ECSS). Dit stelt hen in staat om matches direct te vinden zonder elk paar te hoeven controleren.

Scenario B: Hoge Dimensies (De "Gescheiden" Aanname)

De Setting: Denk aan een enorme, meerdimensionale loods. In hoge dimensies creëert het verdelen van de ruimte in een raster te veel lege tegels (de "vloek van dimensionaliteit").
De Strategie: Ze gebruiken Distributed ID Generation. In plaats van een raster, geven ze elk item een unieke "ID-kaart" op basis van hun locatie.
De Innovatie: Ze hebben een nieuwe manier ontwikkeld om deze ID's veilig te genereren met behulp van hun "Prefix"-truc. Zelfs in een gigantische loods kunnen ze deze ID's zo genereren dat als twee items dicht bij elkaar liggen, hun ID's zullen overeenkomen, zonder de werkelijke locaties van de items te onthullen.

De "Geheime Saus": Equality Conditional Sum

De kern van hun uitvinding is een nieuw wiskundig instrument genaamd Equality Conditional Sum (ECSS).

Hoe het werkt: Stel dat Alice en Bob allebei een lijst met getallen hebben. Ze willen de getallen optellen, maar alleen als aan een specifieke voorwaarde wordt voldaan (bijv. "Tel alleen de getallen op als de prefixes overeenkomen").
De Magie: Ze kunnen deze optelling veilig uitvoeren zonder dat een van beide partijen hun getallen onthult. Als de prefixes niet overeenkomen, is het resultaat slechts willekeurige ruis. Als ze wel overeenkomen, is het resultaat de correcte som. Dit stelt hen in staat om te verifiëren of items dicht bij elkaar liggen zonder ooit de werkelijke waarden te zien.

De Resultaten: Een Enorme Versnelling

De auteurs hebben een werkende versie van hun systeem gebouwd en dit getest tegenover de beste bestaande methoden.

Snelheid: Hun systeem is tot wel 43,7 keer sneller dan de vorige beste methoden.
Dataverbruik: Het gebruikt tot wel 31,3 keer minder data om over het netwerk te verzenden.
Schaalbaarheid: Terwijl andere systemen vastliepen (geen geheugen meer over hadden) wanneer de datasets erg groot werden, bleef hun systeem soepel functioneren.

Samenvatting

Kortom, dit paper lost het "Fuzzy Matching"-probleem op door:

Vervanging van trage, zware encryptie door snelle, lichtgewicht tools.
Het gebruik van "Prefixes" (zoals postcodes) om een trage, lineaire zoektocht om te zetten in een snelle, logaritmische zoektocht.
Het creëren van nieuwe "Geheime Som"-tools die twee partijen in staat stellen om nabijheid te controleren zonder hun geheimen te onthullen.

Het resultaat is een systeem dat "vergelijkbare" items in enorme, private datasets bijna direct kan vinden, wat privacy-bewuste datamatching voor het eerst op grote schaal praktisch maakt.

Technische Samenvatting: Fuzzy PSI vanuit Symmetrische Primitieven met Exact Logaritmische Afhankelijkheid van de Drempelwaarde

Probleemstelling
Fuzzy Private Set Intersection (FPSI) stelt een verzender met een verzameling $d$ -dimensionale vectoren $Q$ en een ontvanger met een verzameling $W$ in staat om items $q \in Q$ te identificeren waarvoor geldt dat er een $w \in W$ bestaat met $\text{dist}(q, w) \le \delta$ , zonder aanvullende informatie prijs te geven. Hoewel standaard PSI een hoge efficiëntie heeft bereikt, kampen bestaande FPSI-protocollen met aanzienlijke theoretische en praktische knelpunten. Eerdere werken vertonen doorgaans een lineaire schaling met de afstandsdrempel $\delta$ (i.e., $O(\delta)$ ), of bereiken slechts een poly-logaritmische afhankelijkheid voor $L_\infty$ -afstanden. Protocollen die algemene Minkowski-afstanden ondersteunen ( $L_p$ voor $p \in [1, \infty]$ ) met een logaritmische afhankelijkheid van $\delta$ hebben ofwel gereageerd op dure Additive Homomorphic Encryption (AHE), of leden aan beveiligingsgebreken en exponentiële complexiteitstermen in de dimensie $d$ . Het doel is om een exacte logaritmische afhankelijkheid op $\delta$ te bereiken voor algemene $L_p$ -afstanden met behulp van uitsluitend efficiënte symmetrische-sleutel primitieven.

Methodologie en Kerntechnieken
De auteurs stellen nieuwe FPSI-protocollen voor die volledig zijn opgebouwd uit Oblivious Transfer (OT) en symmetrische-sleutel primitieven, waarbij publieke-sleutel operaties zoals AHE worden vermeden. De constructie rust op twee primaire assumpties: de apart assumptie (geschikt voor laag-dimensionale settings) en de separate assumptie (geschikt voor hoog-dimensionale settings).

Prefix-representatie en Interval-testen:
De kerninnovatie vervangt de enumeratie van alle integers in een interval $[q_k - \delta, q_k + \delta]$ (wat $O(\delta)$ kost) door een prefix-representatie met behulp van $O(\log \delta)$ prefixes. Dit vermindert de kosten van interval-testen tot $O(\log \delta)$ per dimensie.
Equality Conditional Sum/Inner-Product Share (ECSS/ECIPS):
Om de interactie te beheren die vereist is door prefix-matching zonder de input van de verzender prijs te geven of exponentieel overhead te veroorzaken, introduceren de auteurs twee nieuwe cryptografische primitieven:
- Equality Conditional Sum Share (ECSS): Gebruikt voor $L_\infty$ afstand. Het stelt partijen in staat een som van waarden te berekenen onder conditie van een gelijkheid-match tussen input-vectoren, waarbij secret shares van het resultaat worden uitgegeven.
- Equality Conditional Inner-Product Share (ECIPS): Gebruikt voor algemene $L_p$ afstanden. Het berekent een inwendig product onder conditie van gelijkheid, wat de berekening van $|w_k - q_k|^p$ mogelijk maakt via binomiale expansie zonder de specifieke termen prijs te geven.
  Beide primitieven zijn efficiënt geïmplementeerd met behulp van OT, Oblivious Programmable PRFs (OPPRF) en Permute+Share (PS) protocollen.
Afhandeling van Meerdere Elementen:
- Laag-dimensionaal ( $L_\infty$ en $L_p$ ): De protocollen maken gebruik van spatial hashing (grid cells) gecombineerd met Cuckoo hashing om het aantal paarwijze vergelijkingen te verminderen. De auteurs introduceren optimalisaties met behulp van shared OPRF (sOPPRF) om de noodzaak voor dummy-waarden in lege bins te elimineren, waardoor de hashing-posities van de verzender verborgen blijven en de noodzaak voor globale permutatie-stappen in bepaalde configuraties wordt weggenomen.
- Hoog-dimensionaal ( $L_\infty$ en $L_p$ ): Om de exponentiële $O(2^d)$ kosten van spatial hashing te vermijden, gebruiken de auteurs een Distributed ID Generation (dIDG) protocol. Dit protocol genereert unieke ID's voor elementen zodanig dat nabijgelegen elementen een ID delen. De auteurs identificeren beveiligingsgebreken in recente dIDG-constructies (specifiek in [DZL25]) gerelateerd aan collision leakage en stellen een veilige, symmetrische-sleutel gebaseerde dIDG voor met behulp van sOPPRF en ECSS.

Kernbijdragen

Nieuwe Primitieven: De introductie van ECSS en ECIPS, die efficiënte fuzzy matching mogelijk maken met een exacte logaritmische afhankelijkheid van $\delta$ met uitsluitend symmetrische primitieven.
Optimale Complexiteit: De eerste FPSI-protocollen voor algemene $L_p \in [1, \infty]$ afstanden die een strikt logaritmische complexiteit $O(d \log \delta)$ bereiken in de drempelwaarde $\delta$ . Dit is theoretisch optimaal, aangezien het onderscheiden van waarden in een interval van lengte $O(\delta)$ $\Omega(\log \delta)$ bits aan informatie vereist.
Beveiliging en Efficiëntie: De protocollen elimineren de afhankelijkheid van AHE door dit te vervangen door OT en symmetrische-sleutel operaties. De auteurs identificeren en herstellen ook beveiligingskwetsbaarheden in recente prefix-gebaseerde protocollen (bijv. [DZL25]) die leden aan mask reuse en collision leakage.
Schaalbare Constructies: Gescheiden constructies voor laag-dimensionale (met gebruik van spatial hashing) en hoog-dimensionale (met behulp van dIDG) settings, die beide een optimale asymptotische complexiteit bereiken.

Experimentele Resultaten
De auteurs hebben hun protocollen geïmplementeerd en vergeleken met state-of-the-art werken ([GQL+24], [DZL25], [BGMP25]).

Prestaties: De nieuwe protocollen presteren aanzienlijk beter dan de eerdere stand van de techniek ([GQL+24], [DZL25], [BGMP25]). In laag-dimensionale settings bereiken ze tot 43,7× snellere runtime en 31,3× lagere communicatie overhead.
Schaalbaarheid: Terwijl eerdere werken zoals [GQL+24] en [DZL25] te maken kregen met geheugenoverloop bij set-groottes van $2^{16}$ in hoog-dimensionale settings, werden de voorgestelde protocollen succesvol uitgevoerd onder dezelfde configuraties.
Drempelwaarde Afhankelijkheid: De experimenten bevestigen dat de runtime en communicatiekosten logaritmisch schalen met $\delta$ , in tegenstelling tot de lineaire schaling die wordt waargenomen in eerdere protocollen met lineaire afhankelijkheid.

Betekenis
Het artikel claimt een theoretische doorbraak in optimale drempelwaarde-schaling voor FPSI, waarbij wordt aangetoond dat een exacte logaritmische afhankelijkheid van $\delta$ haalbaar is voor algemene $L_p$ -afstanden zonder kostbare publieke-sleutel cryptografie. Praktisch gezien versnelt dit de haalbaarheid van schaalbare FPSI-toepassingen in domeinen die fuzzy matching vereisen, zoals genomische sequentie-matching, vergelijkbare beeldextractie en detectie van gecompromitteerde credentials, door de efficiëntie-bottlenecks geassocieerd met de afstandsdrempel en dimensionaliteit weg te nemen.