Multi-user Pufferfish Privacy

Titel: Multi-user Pufferfish Privacy

Auteurs: Ni Ding, Songpei Lu, Wenjing Yang, Zijian Zhang.
Context: Onderzoek naar privacy in multi-user systemen waarbij gebruikers stochastische (willekeurige) data rapporteren voor geaggregeerde queries.

1. Het Probleem

Traditionele differentieel privacy (Differential Privacy - DP) gaat vaak uit van deterministische databases, waarbij elke gebruiker een vaste waarde rapporteert. In veel moderne scenario's (zoals federated learning, lokale privacy, of sensibele enquêtes) is data echter inherent stochastisch: gebruikers rapporteren waarden die variëren volgens een kansverdeling.

De uitdaging die dit artikel adresseert, is het garanderen van individuele ononderscheidbaarheid in een multi-user systeem waarbij:

1. Gebruikers een willekeurige variabele rapporteren.
2. Gebruikers het systeem kunnen verlaten of worden vervangen door anderen met verschillende statistische eigenschappen.
3. De privacy moet worden gewaarborgd tegen een geavanceerde tegenstander die voorafgaande kennis (priors) heeft over de systemen.

Het doel is om te bepalen hoe men Laplace-ruis moet kalibreren (hoeveel ruis toevoegen) om Pufferfish Privacy te bereiken. Pufferfish Privacy is een generalisatie van differentieel privacy die rekening houdt met intrinsieke correlaties en stochastische processen in de data.

2. Methodologie

De auteurs hanteren het Pufferfish Privacy-framework en combineren dit met de Kantorovich-methode (gerelateerd aan de 1e-orde Wasserstein-metriek) voor ruiskalibratie.

• Systeemmodel: Een database $D$ bestaat uit $N$ gebruikers. Elke gebruiker $i$ rapporteert een realization van een willekeurige variabele $D_i$. De query is een sommatie: $X = \sum D_i$.
• Geheime Paren (Secret Pairs): Privacy wordt gedefinieerd door de ononderscheidbaarheid tussen specifieke paren van "geheime" scenario's ($s_i, s_j$). De auteurs analyseren vier categorieën van geheime paren:
  1. $S_{a,b}$: Twee verschillende waarden die een gebruiker rapporteert (bijv. $D_i=a$ vs $D_i=b$).
  2. $S_{a,\perp}$: Een gebruiker rapporteert een waarde $a$ versus de afwezigheid van de gebruiker.
  3. $S_{P,\perp}$: Een gebruiker is aanwezig met een specifieke kansverdeling $P_i$ versus afwezigheid.
  4. $S_{P,Q}$: Een gebruiker is aanwezig met verdeling $P_i$ versus een andere verdeling $Q_i$ (of vervanging door een andere gebruiker).
• Ruismechanisme: Er wordt Laplace-ruis $N_\theta$ toegevoegd aan het antwoord ($Y = X + N_\theta$). De schaalparameter $\theta$ moet zodanig worden gekozen dat de verhouding tussen de kansen op een uitkomst onder twee verschillende geheimen binnen de grenzen van $\epsilon$ blijft.
• Kantorovich-benadering: In plaats van de complexere $\infty$-Wasserstein-metriek te gebruiken, maken de auteurs gebruik van de 1-Wasserstein-metriek (Kantorovich). Dit stelt hen in staat om de optimale transportplannen ($\pi^*$) direct te berekenen op basis van cumulatieve verdelingsfuncties (CDF's), wat leidt tot efficiëntere en scherpere sufficientievoorwaarden.

3. Belangrijkste Bijdragen

De paper levert de volgende theoretische en praktische bijdragen:

1. Onafhankelijkheid van andere gebruikers: Het meest opvallende resultaat is dat de sufficientievoorwaarden voor het bereiken van Pufferfish Privacy alleen afhankelijk zijn van de statistieken van de betreffende gebruiker en niet van de aanwezigheid of data van de andere gebruikers in het systeem. Dit geldt zelfs als er een aanwezigheidskans ($\zeta_i$) voor gebruikers wordt geïntroduceerd.
2. Afgeleide Voorwaarden voor Ruis:
   • Voor $S_{a,b}$ (waarde-verandering): De ruis $\theta$ moet evenredig zijn met het absolute verschil $|a - b|$.
   • Voor $S_{a,\perp}$ (aanwezigheid/afwezigheid): De ruis moet evenredig zijn met de waarde $|a|$ (afwezigheid wordt gelijkgesteld aan het rapporteren van 0).
   • Voor $S_{P,\perp}$ en $S_{P,Q}$ (verdeling-verandering): De auteurs leiden een voorwaarde af gebaseerd op de verwachting van de exponentiële functie van de data ($E[e^{|D_i|/\theta}] \leq e^\epsilon$).
3. Verslapte Voorwaarden voor Binair Data: Voor Bernoulli-verdelingen (binair data) tonen de auteurs aan dat de sufficientievoorwaarden kunnen worden verslapt (relaxed). Door gebruik te maken van de specifieke structuur van de binomiale verdeling en numerieke methoden (zoals de Brent-methode), kan een kleinere $\theta$ worden gevonden dan de conservatieve bovenste grens. Dit resulteert in minder ruis en betere data-utility.
4. Efficiënte Berekening: De paper biedt een methode om de maximale afstand in het support van het optimale transportplan direct te berekenen zonder de volledige joint-distributie te hoeven oplossen, wat de toepasbaarheid vergroot.

4. Resultaten en Experimenten

De auteurs valideren hun theorie met experimenten op drie real-world datasets uit de UCI Machine Learning Repository: Adult, Bank Marketing en Student Performance.

• Scenario's: Ze simuleerden het toevoegen, verwijderen of wijzigen van een klasse van gebruikers (bijv. alle personen met een bepaalde etniciteit of huwelijkse status).
• Vergelijking: Ze vergeleken de vereiste ruis ($\theta$) tussen de standaard methode (gebaseerd op maximale waarden) en de verslapte methode (gebaseerd op de verwachtingswaarde/Brent-methode).
• Uitkomsten:
  • De verslapte voorwaarden (vooral voor $S_{P,\perp}$ en $S_{P,Q}$) leiden tot een significante reductie in de hoeveelheid toegevoegde ruis, vooral bij strikte privacy-budgetten (kleine $\epsilon$).
  • Dit betekent een aanzienlijke verbetering in de data-utility (nuttigheid van de data) terwijl dezelfde privacygaranties worden gehandhaafd.
  • De resultaten bevestigen dat de privacyvoorwaarden inderdaad onafhankelijk zijn van de aanwezigheidskansen ($\zeta_i$) van de gebruikers.

5. Significantie en Conclusie

Dit onderzoek is significant omdat het de kloof overbrugt tussen de theoretische Pufferfish Privacy en de praktische implementatie in dynamische, multi-user systemen met stochastische data.

• Praktische Toepasbaarheid: Het biedt data-curators een concrete formule om ruis te kalibreren wanneer gebruikers niet alleen hun waarde wijzigen, maar ook wanneer ze het systeem verlaten of wanneer hun onderliggende data-distributie verandert.
• Efficiëntie: Door te laten zien dat de privacy-vereisten lokaal zijn (afhankelijk van de individuele gebruiker) en niet globaal (afhankelijk van de hele database), wordt de schaalbaarheid van privacymechanismen vergroot.
• Utility-Privacy Trade-off: De introductie van verslapte voorwaarden voor specifieke verdelingen (zoals binair data) biedt een nieuwe route om de klassieke afweging tussen privacy en data-nuttigheid te optimaliseren.

Samenvattend biedt dit artikel een robuust wiskundig raamwerk voor het beschermen van individuele privacy in complexe, probabilistische omgevingen, met bewezen voordelen voor de bruikbaarheid van de gegenereerde data.