Technische Samenvatting: Metrische Differentieel Privaat via de Earth Mover's Distance op Gebruikersniveau

Probleemstelling

Differentieel Privaat (DP) is de standaard geworden voor data-analyse, waarbij traditioneel elke set van invoerdatasets als even gevoelig wordt behandeld. Echter, in veel praktische toepassingen vertoont data heterogeniteit; bijvoorbeeld is het onthullen van de exacte woonplaats van een gebruiker gevoeliger dan het onthullen van het land van herkomst. Metrische Differentieel Privaat (Metric DP) adresseert dit door de privacygarantie lineair te laten afnemen met de afstand tussen invoerparen, wat zorgt voor een betere bruikbaarheid (utility) wanneer inputs vergelijkbaar zijn.

Terwijl eerder werk in Metric DP zich richtte op de item-niveau setting (waarbij elke gebruiker één enkel data-item bijdraagt), bevatten real-world scenario's vaak gebruikers-niveau bijdragen, waarbij een enkele gebruiker een collectie items levert (bijv. een geschiedenis van locaties of een verzameling woorden). Bestaande user-level DP frameworks vertrouwen op standaard DP, waarbij alle wijzigingen aan de volledige dataset van een gebruiker als even gevoelig worden beschouwd, ongeacht de omvang of de aard van de wijziging. Dit artikel initieert de studie naar Metric DP op gebruikersniveau, specifiek gebruikmakend van de Earth Mover's Distance (dEM) als de onderliggende metriek. Het doel is om een privacy-notie te definiëren waarbij de gevoeligheid van de bijdrage van een gebruiker afhangt van zowel het deel van de data dat is gewijzigd als de afstand van die wijzigingen, wat een meer genuanceerde privacy-semantiek biedt dan standaard user-level DP.

Methodologie

1. Definiëren van dEM-DP

De auteurs definiëren dEM-DP door de afstand tussen twee gebruikersdatasets $K$ en $K'$ te meten met behulp van de Earth Mover's Distance (ook bekend als de 1-Wasserstein afstand).

• Metriek: $d_{EM}(\tilde{K}, \tilde{K}')$ vertegenwoordigt de minimale kosten om de waarschijnlijkheidsverdeling van dataset $K$ naar $K'$ te transporteren, waarbij de kosten gelijk zijn aan de hoeveelheid verplaatste data vermenigvuldigd met de afstand $d_X$ tussen de items.
• Privacygarantie: Een mechanisme $M$ voldoet aan $(\alpha, \delta)$-gebonden dEM-DP voor elke twee datasets $K, K'$ van dezelfde grootte:
  $$\Pr[M(K) \in O] \le e^{\alpha \cdot d_{EM}(\tilde{K}, \tilde{K}')} \Pr[M(K') \in O] + \delta$$
  Hierbij schaalt de privacyparameter met de afstand. Als $d_{EM}$ klein is (vergelijkbare datasets), is de privacygarantie sterker (lagere effectieve $\epsilon$) vergeleken met standaard DP, die een uniforme $\epsilon$ zou toepassen.

2. Mechanismeontwerp

Het paper stelt twee nieuwe mechanismen voor voor het vrijgeven van queries onder dEM-DP in zowel het Lokale Model (gebruikers privatiseren data voordat ze deze verzenden) als het Centrale Model (een vertrouwde aggregator houdt de data vast).

A. Lineaire Queries (PrivEMDLinear)

Voor lineaire queries van de vorm $F\tilde{K}$, analyseren de auteurs de gevoeligheid onder dEM.

• Gevoeligheidsanalyse: In tegenstelling tot standaard DP, waarvoor vereist is dat de queryfunctie begrensd is, vereist dEM-DP analyse dat de functie $f$ (die de query representeert) Lipschitz-continu is.
• Resultaat: De auteurs bewijzen dat de gevoeligheid van een lineaire query onder dEM begrensd wordt door de Lipschitz-constante van de queryfunctie. Dit maakt het mogelijk om gekalibreerde ruis toe te voegen (bijv. met behulp van het K-norm mechanisme of het Gaussische mechanisme) die proportioneel is aan de Lipschitz-constante in plaats van een worst-case globale grens, wat de bruikbaarheid verbetert.

B. Ongeordende Item-gewijze Queries (PrivEMDItemWise)

Voor het vrijgeven van een verzameling ruisige outputs voor elk item in een gebruikersdataset (bijv. een histogram), past het mechanisme een basis item-niveau metric DP mechanisme $A$ toe op elk item en shuffelt vervolgens de resultaten.

• Privacy-amplificatie door Shuffling: De auteurs generaliseren het resultaat van "privacy-amplificatie door shuffling" naar de metric DP setting. Omdat de output een ongeordende lijst is, kan een tegenstander specifieke outputs niet koppelen aan specifieke input-indices.
• Technische Nieuwigheid: Ze bewijzen dat het shuffelen van $m$ items de privacykosten vermindert van $O(m\alpha)$ (via compositie) naar $O(\alpha\sqrt{m})$. Dit resultaat wordt afgeleid door de koppeling tussen inputvectoren te analyseren en gebruik te maken van de eigenschappen van het shuffle-model.

3. Extensie naar Onbegrensde Data

Real-world datasets hebben vaak variërende groottes per gebruiker (onbegrensde setting), wat de dEM-analyse bemoeilijkt omdat de grootte van de dataset zelf een privacyprobleem wordt.

• Reductie: De auteurs stellen een black-box reductie voor van onbegrensde naar begrensde dEM-DP.
• Mechanisme: Ze gebruiken sampling met vervanging om elke gebruikersdataset te projecteren op een vaste grootte $s$. Ze bewijzen dat deze projectie "smooth" is, wat betekent dat de dEM-afstand tussen de geprojecteerde datasets dicht bij de dEM-afstand tussen de originele datasets ligt (tot een kleine additieve factor).
• Discrete dEM-DP: Om de additieve fout van sampling op te vangen, introduceren ze een "discrete" definitie van dEM-DP waarbij wijzigingen met een afstand $\le r$ uniform worden beschermd. Ze tonen aan dat voor voldoende grote steekproefgroottes, onbegrensde dEM-DP gereduceerd kan worden tot begrensde dEM-DP met een verwaarloosbaar verlies in privacy-semantiek.

Belangrijkste Bijdragen

1. Definitie van User-Level Metric DP: Het paper stelt een formele definitie vast van Metric DP op gebruikersniveau met behulp van de Earth Mover's Distance, waarbij zowel de omvang als de ruimtelijke aspecten van datawijzigingen worden gevangen.
2. Nieuwe Mechanismen:
   • PrivEMDLinear: Een mechanisme voor lineaire queries dat gebruikmaakt van Lipschitz-continuïteit om gevoeligheid te begrenzen, wat een betere bruikbaarheid biedt dan standaard user-level DP voor specifieke querytypes.
   • PrivEMDItemWise: Een algemeen mechanisme voor item-gewijze queries dat shuffling gebruikt. De auteurs bieden een gegeneraliseerde privacy-amplificatie analyse die een $\sqrt{m}$ verbetering laat zien ten opzichte van standaard compositie-bounds.
3. Onbegrensde Reductie: Een black-box reductietechniek die begrensde dEM-DP mechanismen omzet in onbegrensde mechanismen via sampling, waardoor deze mechanismen toepasbaar worden op datasets met variabele omvang van gebruikersbijdragen.
4. Verbeteringen in Bruikbaarheid (Utility): Theoretische analyses tonen aan dat dEM-DP mechanismen een strikt betere bruikbaarheid (lagere fout) kunnen bereiken dan standaard user-level DP baselines voor:
   • Lineaire Embedding Queries: In zowel centrale als lokale modellen, met name wanneer de privacyparameter $\alpha$ groter mag zijn dan de standaard $\epsilon$ voor dissimilar inputs.
   • Frequentie-estimatie: In het lokale model is de fout verbeterd wanneer de domeingrootte en de privacyparameters aan specifieke condities voldoen, waarbij gebruik wordt gemaakt van het feit dat alleen "nabije" items (binnen clusters) sterke privacy vereisen.

Resultaten en Betekenis

Het paper claimt dat dEM-DP een fijnmaziger privacydefinitie biedt die beter aansluit bij real-world privacy-semantiek.

• Privacy-semantiek: In standaard DP wordt een wijziging in de data van een gebruiker voor een hele maand als even gevoelig behandeld als een wijziging voor een enkele dag. In dEM-DP wordt de wijziging van een enkele dag als minder gevoelig beschouwd (kleinere $d_{EM}$), wat minder ruis en hogere bruikbaarheid toelaat, terwijl de wijziging van een hele maand een sterkere garantie krijgt.
• Bruikbaarheidswinsten: Theoretische bounds laten zien dat dEM-DP mechanismen standaard user-level DP kunnen overtreffen voor lineaire embedding queries en frequentie-estimatie. Bijvoorbeeld, bij frequentie-estimatie is de foutafhankelijkheid van de domeingrootte $k$ en de privacyparameter verbeterd onder dEM-DP wanneer de data structuur vertoont (bijv. geclusterde metrieken).
• Generaliseerbaarheid: De reductie naar begrensde settings en de algemene shuffling-analyse suggereren dat deze technieken breed toegepast kunnen worden op diverse metriekruimtes en querytypes buiten de specifieke voorbeelden (locatie, tekst, grafen) die worden gegeven.

De auteurs positioneren dit werk als het eerste dat een algemene definitie van user-level Metric DP via dEM voorstelt, waarbij zij verder gaan dan specifieke tekstgebaseerde toepassingen naar een framework dat toepasbaar is op algemene metriekruimtes. Zij benadrukken dat hoewel dEM-DP een relaxatie is van standaard DP, het een meer praktische afweging biedt voor toepassingen waar de gelijkenis van data correleert met de gevoeligheid.