💻 computer science

Efficient Fuzzy PSI under One-Sided Assumptions

Dit artikel introduceert de eerste concreet efficiënte fuzzy private set intersection-protocollen voor algemene $L_p$ -afstanden onder eenzijdig gebaseerde aannames, waarbij gebruik wordt gemaakt van lichtgewicht symmetrische cryptografische primitieven en prefix trie-technieken om een $O(\log \delta)$ -complexiteit te bereiken en eerdere state-of-the-art werken aanzienlijk te overtreffen in zowel computationele snelheid als communicatieoverhead.

Oorspronkelijke auteurs: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

Gepubliceerd 2026-08-19

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Xinpeng Yang, Meng Hao, Yanxue Jia, Chenkai Weng, Yonggang Wen, Tianwei Zhang

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

In het digitale tijdperk moeten twee organisaties vaak een gemeenschappelijk grondgebied vinden zonder al hun geheimen aan elkaar te onthullen. Stel je een ziekenhuis voor dat een lijst heeft van patiënten met een specifieke aandoening en een onderzoeksinstituut dat een lijst heeft van vrijwilligers. Ze willen weten welke vrijwilligers ook patiënten zijn, maar geen van beide partijen wil hun volledige lijst overhandigen, omdat dat de privédata van iedereen op de lijst zou blootstellen. Standaard computereprotocollen kunnen dit exacte matchingsprobleem efficiënt oplossen, maar ze falen wanneer de data een beetje rommelig is. In de echte wereld zijn namen verkeerd gespeld, locaties wijken licht af en biometrische scans variëren van dag tot dag. Als het dossier van het ziekenhuis "John Smith" zegt en het dossier van de vrijwilliger zegt "Jon Smyth", ziet een standaard systeem geen match, ook al zijn ze dezelfde persoon. Hier komt "fuzzy" matching om de hoek kijken, een methode die ontworpen is om deze benaderende verbindingen te vinden. Het doen van dit proces op een veilige manier is echter ongelooflijk moeilijk. Als het systeem probeert elke mogelijke variatie van elke naam te vergelijken met elke andere variatie, wordt de hoeveelheid uitgewisselde data zo massief dat het proces tot stilstand komt, of vereist het zulke zware wiskundige machines dat het onpraktisch wordt voor dagelijks gebruik.

Een team van onderzoekers heeft nu een nieuwe manier ontwikkeld om deze fuzzy matching uit te voeren die zowel snel als lichtgewicht is. Hun werk richt zich op een scenario waarbij slechts één van de twee partijen strikte regels hoeft te volgen over hoe hun data is gerangschikt, terwijl de andere partij data in een willekeurige volgorde kan hebben. Eerdere pogingen om dit probleem onder dergelijke versoepelde omstandigheden op te lossen, vertrouwden op zware, trage cryptografische tools of vereisten dat beide partijen over perfect georganiseerde data beschikten, wat in de werkelijkheid zelden het geval is. De nieuwe methode, gecreëerd door Xinpeng Yang en collega's van instellingen in Singapore en de Verenigde Staten, bereikt hetzelfde doel met behulp van eenvoudige, snelle bouwstenen. Ze slaagden erin de tijd en de data die nodig zijn voor deze vergelijkingen met enorme marges te verminderen, waardoor veilige, benaderende matching voor het eerst haalbaar werd in veel real-world settings.

De kern van de prestatie ligt in de manier waarop de onderzoekers de "afstand" tussen datapunten afhandelen. In deze context is afstand een maatstaf voor hoe verschillend twee stukjes informatie zijn, zoals hoeveel letters er verschillen tussen twee namen of hoe ver twee GPS-coördinaten uit elkaar liggen. Het doel is om paren te vinden waar de afstand kleiner is dan een specifieke drempelwaarde. De onderzoekers realiseerden zich dat eerdere methoden probeerden elke mogelijke variatie van een datapunt te controleren, wat een zoekruimte creëerde die explosief groeide naarmate de toegestane afwijking toenam. Om dit op te lossen, introduceerden ze een techniek die werkt als een slim filter. In plaats van elke mogelijke variatie te controleren, organiseert het systeem de data in een boomstructuur waarmee het enorme blokken irrelevante informatie direct kan overslaan. Deze verandering verminderde de computationele inspanning van een niveau dat exponentieel groeide met de grootte van de zoekopdracht naar een niveau dat slechts logaritmisch groeit. In praktische termen betekent dit dat zelfs als de toegestane afwijking tussen datapunten wordt verdubbeld of verdrievoudigd, de tijd die nodig is om de controle uit te voeren nauwelijks toeneemt.

Het team testte hun nieuwe protocollen tegen de beste bestaande methoden die momenteel beschikbaar zijn. De resultaten waren spectaculair. Wanneer vergeleken met een recent protocol uit 2024, draaide hun nieuwe systeem tot 239 keer sneller en gebruikte het tot 20 keer minder communicatiebandbreedte. Tegenover een methode uit 2025 bereikte de versnelling 518 keer, met een 63-voudige reductie in dataoverdracht. In één specifieke vergelijking met een andere constructie uit 2025, was het nieuwe systeem bijna 5.000 keer sneller en vereiste het 282 keer minder communicatie. Deze cijfers waren niet alleen theoretisch; de onderzoekers implementeerden het volledige systeem en voerden uitgebreide experimenten uit over een breed scala aan datagrootten en instellingen. Ze bevestigden dat hun aanpak werkt of nu de verzender of de ontvanger degene is met de georganiseerde data, en dat het diverse soorten afstandmetingen ondersteunt, niet alleen de eenvoudige.

Een belangrijke innovatie in hun werk was het vermogen om "éénzijdige" aannames te hanteren. In veel eerdere beveiligde systemen moesten beide partijen zich aan strikte regels houden, zoals het waarborgen dat hun datapunten ver genoeg uit elkaar lagen om verwarring te voorkomen. Dit is vaak onmogelijk in het echte leven, waar data in clusters of willekeurige patronen binnenkomt. De nieuwe methode vereist alleen dat één zijde een enigszien georganiseerde dataset heeft, terwijl de andere zijde volledig willekeurige, rommelige data kan hebben. Deze flexibiliteit maakt de technologie toepasbaar op scenario's zoals contactonderzoek of locatiegebaseerde diensten, waarbij de ene entiteit een gestructureerde database van bekende locaties kan hebben terwijl de andere een stroom van ongestructureerde gebruikersinput heeft. Door uitsluitend te vertrouwen op lichtgewicht, symmetrische sleuteltechnieken — in essentie snelle en efficiënte standaard encryptietools — vermeden de onderzoekers de zware, trage wiskundige operaties die vergelijkbare inspanningen voorheen vertraagden.

De onderzoekers verkenden ook hoe ze het systeem nog efficiënter kunnen maken wanneer de data schaars is, wat betekent dat de punten verspreid zijn in plaats van geclusterd. In deze gevallen ontdekten ze dat het wisselen van de rollen van de twee partijen in het matchingproces de workload verder kon balanceren en de prestaties kon verbeteren. Deze aanpasbaarheid suggereert dat het systeem kan worden afgestemd op verschillende soorten toepassingen zonder dat er een volledige herontwerp nodig is. Het werk demonstreert dat het mogelijk is om beveiligde, privacy-beschermende systemen te bouwen die niet alleen theoretisch solide zijn, maar ook praktisch snel genoeg voor real-world deployment.

De implicaties van dit werk reiken verder dan alleen snelheid. Door fuzzy matching efficiënt te maken, hebben de onderzoekers de deur geopend voor meer geavanceerde privacy-beschermende toepassingen. Organisaties die lang hebben geweigerd gegevens te delen uit angst voor privacylekken of omdat het matchingproces te traag was, kunnen nu beveiligde samenwerking overwegen. Of het nu gaat om het matchen van patiëntendossiers voor medisch onderzoek, het verifiëren van gebruikersidentiteiten zonder biometrische sjablonen bloot te leggen, of het vinden van vergelijkbare items in grote catalogi zonder de inhoud van de catalogus te onthullen: de drempel voor deelname is aanzienlijk verlaagd. De studie bewijst dat met de juiste algoritmische aanpak de afruil tussen privacy en prestaties kan worden opgelost, waardoor data veilig kan stromen, zelfs wanneer deze imperfect of ruizig is.

Uiteindelijk presenteert het artikel een concrete oplossing voor een probleem dat al jaren voortduurt: hoe vind je benaderende matches in privédata zonder snelheid op te offeren of onrealistische voorwaarden te stellen. De onderzoekers hebben niet alleen een nieuw idee voorgesteld; ze hebben het gebouwd, getest en aangetoond dat het alles wat eraan voorafging met ordes van grootte overtreft. Hun werk staat als een testament voor de kracht van het verfijnen van de onderliggende logica van een probleem, in plaats van simpelweg meer rekenkracht te proberen te gebruiken. Voor de geïntrigeerde observator is het resultaat een systeem dat minder aanvoelt als een zware, logge machine en meer als een precieze, efficiënte tool, klaar om te worden gebruikt in de rommelige, imperfecte wereld van echte data.

Technische Samenvatting: Efficiënte Fuzzy PSI onder Eenzijdige Aannames

Probleemstelling

Fuzzy Private Set Intersection (PSI) stelt twee partijen, een zender en een ontvanger, in staat om elementen in hun respectieve invoersets te identificeren die ongeveer overeenkomen. Specifiek leert de ontvanger, gegeven een afstandsdrempel $\delta$ en een metriek $dist(\cdot, \cdot)$ , alle zender-elementen $\mathbf{q}$ waarvoor er een ontvanger-element $\mathbf{w}$ bestaat zodanig dat $dist(\mathbf{q}, \mathbf{w}) \le \delta$ .

Terwijl standaard PSI aanzienlijke vooruitgang heeft geboekt, kampt fuzzy PSI met een afruil tussen efficiëntie en de sterkte van de onderliggende aannames. Bestaande constructies voor algemene $L_p$ ( $p \in [1, \infty]$ ) afstanden vallen doorgaans in twee categorieën:

Tweezijdige aannames: Protocollen waarbij beide partijen' inputs moeten voldoen aan sterke geometrische scheiding (bijv. punten zijn paargewijs gescheiden door $2\delta$ of $4\delta$ ). Deze zijn efficiënt maar vaak onrealistisch voor real-world ruisgevoelige data.
Eenzijdige aannames: Protocollen waarbij slechts één partij' inputs aan scheidingsrestricties moet voldoen, waardoor de andere partij willekeurige inputs kan hebben. Echter, bestaande eenzijdige oplossingen vertrouwen ofwel op zware cryptografische primitieven (bijv. Additive Homomorphic Encryption) of brengen substantiële asymptotische overhead met zich mee in de drempel $\delta$ (bijv. $O(\delta)$ of $O((\log \delta)^d)$ ).

De kernuitdaging die wordt aangepakt, is het construeren van concreet efficiënte fuzzy PSI-protocollen voor algemene $L_p$ -afstanden onder zwakke eenzijdige aannames, waarbij uitsluitend gebruik wordt gemaakt van lichtgewicht symmetrische-sleutel primitieven.

Methodologie

De auteurs stellen een framework voor dat gebouwd is op Secret-Shared Oblivious Programmable Pseudorandom Functions (so-OPPRF) en Spatial Hashing, versterkt door Prefix Trie technieken.

1. Multi-Point Fuzzy Matching Primitieven

Om willekeurige inputs van één partij zonder lekken te kunnen afhandelen, introduceert het paper twee aanname-vrije multi-point fuzzy matching protocollen:

1-naar- $n$ Matching (Ontvanger houdt willekeurige punten): De zender programmeert een so-OPPRF met intervallen rond zijn enkele punt. Om te voorkomen dat de ontvanger de distributie van de zender-input afleidt via botsingen in geaggregeerde shares (een lekprobleem in eerder werk), introduceren de auteurs Equality-conditional Randomization (EqRand). Deze primitief her-randomiseert de geheime shares voor niet-overeenkomende inputs terwijl de correcte som voor overeenkomende inputs behouden blijft, wat privacy garandeert zelfs wanneer meerdere ontvanger-punten naar hetzelfde geprogrammeerde interval mappen.
$m$ -naar-1 Matching (Zender houdt willekeurige punten): De rollen zijn omgedraaid. De ontvanger programmeert de so-OPPRF met intervallen rond zijn enkele punt. De zender evalueert de functie op zijn meerdere punten. Omdat de ontvanger de geaggregeerde waarden van de zenderzijde niet reconstrueert, wordt het lekprobleem van nature vermeden en is EqRand niet vereist.

2. Fuzzy PSI onder Eenzijdige Aannames

Bouwend op de bovenstaande primitieven, construeren de auteurs volledige $m$ -naar- $n$ fuzzy PSI-protocollen onder twee specifieke eenzijdige aannames:

Unique Cell Assumption: Elke ruimtelijke cel (met een zijde van lengte $2\delta$ ) bevat maximaal één punt van de beperkte partij.
Unique Block Assumption (Sparsere): Elke ruimtelijke cel snijdt met maximaal één $L_\infty$ bal van de beperkte partij.

Het protocol maakt gebruik van spatial hashing om de ruimte te partitioneren. De beperkte partij programmeert de so-OPPRF met sleutels afgeleid van hun punten en cel-identificatoren, wat botsingsvrijheid garandeert. De onbeperkte partij evalueert de functie op hun punten en naburige cellen. Het gebruik van so-OPPRF zorgt ervoor dat outputs geheim gedeeld worden, waardoor geen van beide partijen de ruwe data van de ander leert.

3. Prefix Trie Optimalisatie

Om de lineaire of superlineaire complexiteit die schaalt met $\delta$ in eerdere werken aan te pakken, integreren de auteurs Prefix Trie technieken.

Mechanisme: In plaats van alle punten in een interval $[w - \delta, w + \delta]$ te enumereren (wat $O(\delta)$ kost), wordt het interval gecodeerd in $O(\log \delta)$ prefix nodes met behulp van het PxTrie algoritme.
Dimensie-voor-dimensie Filtering: Eerdere werken vereisten het evalueren van alle combinaties van prefixes over $d$ dimensies, wat leidde tot een $O((\log \delta)^d)$ complexiteit. De auteurs introduceren een Conditional Selection (ConSel) primitief die prefixes dimensie-voor-dimensie filtert. Omdat maximaal één prefix per dimensie kan matchen met het doel, wordt de zoekruimte teruggebracht van $O((\log \delta)^d)$ naar $O(d \cdot \log \delta)$ .
Resultaat: Dit bereikt een $O(\log \delta)$ complexiteit in de drempel $\delta$ voor algemene $L_p$ afstanden, een significante verbetering ten opzichte van de voorheen geldende $O((\log \delta)^d)$ of $O(\delta)$ bounds.

4. Afhandeling van Algemene $L_p$ Afstanden

Voor $L_p$ afstanden ( $p > 1$ ) codeert het protocol de $p$ -de macht van de per-dimensie afstand bijdrage ( $|t|^p$ ) in de so-OPPRF waarden. De partijen voeren vervolgens secure multi-party computation uit (optelling en vermenigvuldiging) om deze shares te aggregeren en te controleren of de totale afstand binnen de drempel $\delta^p$ valt.

Belangrijkste Bijdragen

Eerste Efficiënte Eenzijdige Fuzzy PSI voor Algemene $L_p$ : Het paper presenteert de eerste concreet efficiënte protocollen voor algemene $L_p \in [1, \infty]$ afstanden onder eenzijdige aannames, die uitsluitend vertrouwen op lichtgewicht symmetrische-sleutel primitieven (so-OPPRF, OKVS, silent OT).
Logaritmische Complexiteit in $\delta$ : Door prefix trie technieken niet-triviaal te integreren met een dimensie-voor-dimensie filtering mechanisme, bereiken de protocollen een $O(\log \delta)$ complexiteit in de afstandsdrempel, wat een verbetering is ten opzichte van de $O((\log \delta)^d)$ of $O(\delta)$ complexiteiten van state-of-the-art werken.
Flexibele Ondersteuning van Aannames: Het framework ondersteunt zowel Zender-zijde als Ontvanger-zijde settings, evenals Unique Cell en Unique Block aannames. De Unique Block aanname staat verdere optimalisaties toe door de rollen van programmeren en evalueren om te draaien om de lagere kosten van programmeren versus het evalueren van so-OPPRF te benutten.
Uitgebreide Evaluatie: De auteurs hebben de protocollen geïmplementeerd en vergeleken met state-of-the-art werken (van Baarsen & Pu [31], Dang et al. [10], Bui et al. [6], etc.).

Experimentele Resultaten

De evaluatie werd uitgevoerd op een server met een AMD EPYC 9554 processor. De resultaten tonen significante verbeteringen in zowel communicatie als computation:

Tegenover van Baarsen en Pu (EUROCRYPT'24): Tot 239 $\times$ snellere computation en tot 20 $\times$ lagere communicatie.
Tegenover Dang et al. (CCS'25): Tot 518 $\times$ snelheidswinst en 63 $\times$ reductie in communicatie.
Tegenover Bui et al. (ASIACRYPT'25): Tot 4818 $\times$ snellere computation en tot 282 $\times$ lagere communicatie.

De prefix-geoptimaliseerde varianten (Ours-Px) vertonen superieure prestaties in communicatie voor grote $\delta$ en hoge dimensies, terwijl de niet-geoptimaliseerde varianten (Ours) zeer competitief zijn voor kleinere drempels vanwege de lagere computationele overhead.

Betekenis en Claims

Het paper claimt de langdurige afruil tussen de sterkte van geometrische aannames en de efficiëntie van fuzzy PSI protocollen te hebben opgelost. Door aan te tonen dat algemene $L_p$ fuzzy PSI kan worden bereikt onder zwakke eenzijdige aannames met uitsluitend lichtgewicht symmetrische-sleutel primitieven, maakt dit werk fuzzy PSI toepasbaarder voor real-world scenario's waar data ruis bevat en strikte scheidingsaannames niet gegarandeerd kunnen worden.

De auteurs benadrukken dat hun protocollen eerdere werken onder vergelijkbare aannames aanzienlijk overtreffen, waarbij ze ordes van grootte aan efficiëntieverbetering bereiken. De introductie van het dimensie-voor-dimensie filtering mechanisme via prefix tries wordt benadrukt als een cruciale technische innovatie die de exponentiële afhankelijkheid van dimensionaliteit in de drempelparameter doorbreekt, waardoor de protocollen schaalbaar zijn voor hoog-dimensionale data en grote matching drempels.