Op weg naar een verbeterde efficiënte lekbestendige verbeterde private set union

Waarom het delen van lijsten de privacy kan bedreigen

Veel organisaties bewaren gevoelige lijsten—zoals verdachte IP‑adressen, klant‑ID's of deelnemers aan medische studies—die ze graag met de lijst van een andere partij willen combineren zonder hun eigen gegevens bloot te geven. Een techniek genaamd private set union belooft precies dat: het laat twee partijen de gecombineerde lijst van unieke items leren, en niets meer. Dit artikel toont aan dat zelfs geavanceerde versies van deze techniek tijdens de uitvoering stilletjes extra informatie kunnen lekken, en introduceert een nieuw ontwerp dat de voordelen behoudt terwijl het deze verborgen risico's en de rekencost aanzienlijk vermindert.

Wat private set union probeert te beschermen

Stel je twee bedrijven voor die zwarte lijsten van cyberaanvallen vergelijken. Elk wil uiteindelijk een volledige lijst van alle verdachte IP‑adressen hebben die door één van beiden zijn waargenomen, zodat ze hun netwerken beter kunnen verdedigen. Tegelijkertijd zijn de detectiemethoden van elk bedrijf—en dus hun exacte zwarte lijsten—geheime handelsinformatie. Als iemand zou kunnen afleiden welke adressen de ander wel of niet heeft, kan dat die methoden onthullen. Klassieke private set union‑protocollen verbergen al de directe overlap tussen lijsten, maar recent onderzoek heeft aangetoond dat ze toch aanwijzingen kunnen prijsgeven tijdens de berekening zelf of via patronen in hoe items in interne datastructuren worden gerangschikt.

Verborgen lekken in eerdere snelle methoden

Eerdere schaalbare schema's vertrouwden op een werkwijze die eerst, item voor item, controleerde of elk element uit de ene lijst in de andere voorkwam, en daarna die antwoorden gebruikte om alleen de “nieuwe” items te leveren. Later werk liet zien dat dit proces inherent onthult hoeveel items de lijsten delen voordat het protocol is voltooid. Een nieuwsgierige deelnemer kan dit uitbuiten door de uitvoering af te breken en het protocol opnieuw te draaien met licht aangepaste invoer, en zo geleidelijk te leren welke specifieke items overlappen. Andere snelle schema's gebruikten hashing—het plaatsen van items in bakken op basis van een hashfunctie—om gegevens te ordenen. Zodra één partij weet welke van de andere partij unieke items zijn, kan die partij het patroon van gevulde en lege bakken kruiscontroleren om af te leiden welke van zijn eigen items beslist niet in de andere lijst voorkomen, een vorm van “hash‑gebaseerde” lekkage.

Items vergrendelen achter willekeurige vermommingen

Het nieuwe protocol pakt beide problemen tegelijk aan. Nog voordat er gehasht wordt, voert elke partij een cryptografische uitwisseling uit die elk item in een willekeurig uitziend token verandert. De cruciale eigenschap is dat identieke items uit de twee lijsten in identieke tokens veranderen, terwijl verschillende items ongecorreleerde tokens opleveren—en geen van beide partijen leert de geheime sleutel die tokens terug naar echte waarden verbindt. Deze vermomde tokens worden vervolgens in op hashing gebaseerde tabellen geplaatst en door een reeks zorgvuldig gestructureerde, gerandomiseerde stappen geleid die in feite beslissen of tokens overeenkomen, zonder te onthullen welk token in welke bak zit. Herhaling van dit proces met verse willekeurigheid in elke uitvoering voorkomt dat een aanvaller informatie over meerdere runs kan correleren.

Kosten verminderen met een slimmer datastructuur

Alleen beveiliging is niet voldoende als een protocol te zwaar is om op schaal te gebruiken. De auteurs herontwerpen daarom een van de duurste componenten: een intern onderdeel dat eerder op een gebundelde cryptografische primitief vertrouwde om veel items tegelijk te vergelijken. Ze vervangen dit door een “bidirectionele” oblivious key‑value store, een compacte structuur waarmee de ene partij sleutel‑waardeparen kan coderen zodat de andere ze kan opvragen zonder iets te leren behalve of een sleutel aanwezig is. Door twee van dergelijke coderingen tegen elkaar uit te zetten, kan het protocol vaststellen wanneer tokens over de twee lijsten heen overeenkomen en tegelijk werk op lege of dummy‑bakken vermijden. Deze wijziging vermindert zowel de hoeveelheid verzonden data als de rekentijd aanzienlijk, vooral voor grote lijsten.

Wat de experimenten in de praktijk laten zien

Om hun ideeën te testen implementeerden de auteurs hun protocol en vergeleken het met het beste bestaande verbeterde private set union‑ontwerp onder dezelfde, strengere privacydoelen. Over een breed scala aan lijstgroottes en netwerkcondities verminderde hun methode consequent de communicatie met ongeveer 1,1 tot 3 keer en versnelde de uitvoering met ruwweg 1,0 tot 1,7 keer. Belangrijk is dat deze voordelen ook gelden nadat de extra cryptografische laag is toegevoegd die hash‑gebaseerde lekkage voorkomt, iets wat eerdere efficiënte schema's negeerden. De resultaten suggereren dat sterkere bescherming niet per se met een grote prestatiekost gepaard hoeft te gaan.

Waarom dit belangrijk is voor echte gegevensdeling

Simpel gezegd toont dit werk aan hoe twee partijen gevoelige lijsten kunnen combineren terwijl ze sterk beperken wat elk van hen over de gegevens van de ander kan afleiden—even uit subtiele neveneffecten tijdens het protocol. Door items te vermommen voordat er gehasht wordt en door zuinigere interne structuren te gebruiken, sluit het nieuwe ontwerp bekende lekkanalen af en blijft het snel genoeg voor zeer grote datasets. Dit maakt privacy‑bewaardende verenigingen van zwarte lijsten, klant‑ID's of andere identificatoren praktischer voor bedrijven en instellingen die moeten samenwerken zonder de patronen in hun eigen data bloot te leggen.

Bronvermelding: Liu, Q., Bae, J. & Lee, JW. Towards an improved efficient leakage-resilient enhanced private set union. Sci Rep 16, 10134 (2026). https://doi.org/10.1038/s41598-026-40531-5

Trefwoorden: private set union, gegevensprivacy, cryptografische protocollen, veilige gegevensdeling, lekbestendigheid