Revisiting Locally Differentially Private Protocols: Towards Better Trade-offs in Privacy, Utility, and Attack Resistance

Titel: Revisiting Locally Differentially Private Protocols: Towards Better Trade-offs in Privacy, Utility, and Attack Resistance

Auteurs: H´eber H. Arcolezi en S´ebastien Gambs
Context: Lokale Differentiële Privacy (LDP) voor frequentie-schatting.

---

1. Het Probleem

Lokale Differentiële Privacy (LDP) is een standaard voor privacybescherming in gedecentraliseerde systemen (zoals Google Chrome, Apple iOS), waarbij gebruikers hun data lokaal verstoren voordat deze naar een onbetrouwbare server wordt verzonden. Hoewel veel LDP-protocollen (zoals GRR, OUE, OLH) zijn ontworpen om de nut (utility) te maximaliseren—meestal gemeten als de variantie of Mean Squared Error (MSE) van de frequentieschatting—negeert traditioneel onderzoek vaak de kwetsbaarheid voor adversariale aanvallen.

De huidige protocollen bieden een formele privacygarantie ($\epsilon$-LDP), maar dit garandeert niet dat een aanvaller de oorspronkelijke invoer van een gebruiker niet kan reconstrueren. Er bestaat een fundamenteel spanningsveld tussen:

1. Privacy: Hoe moeilijk is het voor een aanvaller om de echte data te reconstrueren?
2. Nut (Utility): Hoe accuraat is de geschatte frequentieverdeling?
3. Integriteit: Hoe vatbaar is het systeem voor data-vergiftiging (poisoning)?

Bestaande protocollen zijn vaak geoptimaliseerd voor één doel (MSE minimaliseren), wat leidt tot onverwachte kwetsbaarheden waar aanvaller succes (ASR) hoog is, zelfs binnen een strak privacybudget.

2. Methodologie

De auteurs introduceren een algemeen multi-objectief optimalisatiekader om LDP-protocollen te analyseren en te verfijnen. In plaats van alleen naar $\epsilon$ of MSE te kijken, evalueren ze protocollen langs een unificatie-as van privacy, nut en aanvalbaarheid.

Kerncomponenten van de methode:

• Metingen:

  • Privacy: Gemeten via de Attacker Success Rate (ASR) bij data-reconstructie-aanvallen. Dit is de kans dat een aanvaller de originele invoer correct kan raden uit de verstoorde output. De auteurs leiden analytische formules af voor ASR voor acht bestaande protocollen.
  • Nut: Gemeten via de Mean Squared Error (MSE) van de frequentieschatting.
  • Integriteit: Geëvalueerd via Data Poisoning Attacks (Maximal Gain Attack), gemeten als de Expected Poisoning Gain (EPG).

• Analytische Afleidingen:
  De auteurs leiden nieuwe gesloten-vorm vergelijkingen af voor de verwachte ASR van drie protocollen waar dit eerder ontbrak: Summation with Histogram Encoding (SHE), Thresholding with Histogram Encoding (THE) en een generieke Unary Encoding variant.

• Adaptieve Protocollen:
  Ze passen vier bekende protocollen aan door hun interne parameters te optimaliseren voor een balans tussen ASR en MSE, in plaats van alleen MSE. Dit wordt gedaan via multi-objectief optimalisatie met een gewogen som:
  $$\min J(\Theta) = w_{ASR} \cdot ASR + w_{MSE} \cdot MSE$$
  Hierbij worden de parameters (zoals subsetgrootte $\omega$, hash-domein $g$, of drempelwaarde $\theta$) dynamisch gekozen om het Pareto-frontier te verbeteren, terwijl de $\epsilon$-LDP-garantie strikt behouden blijft.

  De nieuwe adaptieve protocollen zijn:

  • ASS (Adaptive Subset Selection)
  • AUE (Adaptive Unary Encoding)
  • ALH (Adaptive Local Hashing)
  • ATHE (Adaptive Thresholding with HE)

3. Belangrijkste Bijdragen

1. Evaluatiekader: Een nieuw, aanvalsbewust benchmarkkader dat privacy-lekkage (ASR) en nut (MSE) gezamenlijk analyseert, wat een meer realistisch beeld geeft dan $\epsilon$ alleen.
2. Analytische Uitbreiding: Afleiding van nieuwe analytische formules voor de ASR van SHE, THE en generieke UE-protocollen, wat theoretisch inzicht biedt in adversariale lekkage.
3. Uitgebreide Experimentele Evaluatie: Een systematische analyse van acht state-of-the-art protocollen over een breed scala aan privacybudgetten ($\epsilon$) en domeingroottes ($k$).
4. Adaptieve Varianties: De introductie van ASS, AUE, ALH en ATHE. Deze varianten tonen aan dat het mogelijk is om de aanvalssuccesrate drastisch te verlagen zonder de nuttigheid onaanvaardbaar te verlagen.
5. Open Source: De code is beschikbaar gesteld om de resultaten te reproduceren en verder onderzoek te faciliteren.

4. Resultaten

De experimentele resultaten, gebaseerd op zowel analytische berekeningen als empirische validatie (met het Adult-dataset), tonen het volgende aan:

• ASR Vermindering: De adaptieve protocollen presteren significant beter dan hun niet-adaptieve tegenhangers. Bijvoorbeeld, ASS beperkt de ASR van het traditionele SS-protocol tot onder de 0,25, terwijl het traditionele SS een ASR van 1 bereikt (volledige reconstructie) bij hogere $\epsilon$-waarden.
• Nut Behoud: Hoewel de adaptieve protocollen een iets hogere MSE hebben dan de geoptimaliseerde state-of-the-art protocollen (zoals OUE of OLH), blijft deze toename binnen acceptabele grenzen (maximaal twee ordes van grootte, vaak veel minder). Ze bieden een veel beter compromis.
• Pareto-Frontier: De adaptieve protocollen verschuiven de Pareto-grens (de optimale trade-off tussen ASR en MSE) naar een gunstiger regio. Ze bereiken combinaties van lage ASR en lage MSE die niet haalbaar zijn door alleen het privacybudget $\epsilon$ aan te passen bij vaste protocollen.
• Integriteit: In de analyse van data-vergiftiging (EPG) blijkt dat de adaptieve protocollen (zoals ALH) niet alleen de reconstructie-risico's verlagen, maar ook vaak een lagere kwetsbaarheid voor vergiftiging vertonen vergeleken met hun oorspronkelijke versies.
• Domeingrootte: De voordelen van de adaptieve protocollen zijn consistent over kleine, middelgrote en grote domeingroottes ($k$).

5. Betekenis en Conclusie

Dit paper biedt een paradigmaverschuiving in het ontwerp van LDP-protocollen. Het demonstreert dat het puur minimaliseren van de schattingsfout (MSE) niet leidt tot de beste privacybescherming tegen reconstructie-aanvallen.

Door een multi-objectief optimalisatiebenadering te adopteren, kunnen ontwikkelaars LDP-protocollen "tunen" die specifiek zijn afgestemd op de dreigingsmodellen van hun toepassing (bijv. meer focus op privacy bij gevoelige data, of meer focus op nut bij minder kritieke data). De adaptieve protocollen (ASS, AUE, ALH, ATHE) bieden een praktische oplossing om de kloof tussen theoretische privacygaranties en reële kwetsbaarheden te overbruggen, waardoor robuustere privacy-systemen kunnen worden ingezet zonder de bruikbaarheid van de data drastisch te offeren.

Kortom: Aanvalsbewust ontwerp is essentieel voor echte privacy. Het paper levert de tools en methoden om dit te realiseren.