Privacy Filters are Captured by Residues: A Characterization of Free Natural Filters and the Cost of Adaptivity

1. Problema e Contesto

Il lavoro si concentra sulla Privacy Differenziale (DP) in scenari di composizione adattiva. In tali scenari, un analista interagisce iterativamente con un curatore dei dati, scegliendo dinamicamente le query e i meccanismi di privacy in base agli esiti delle interazioni precedenti.

Il problema centrale è la gestione del budget di privacy. I "Privacy Filters" (filtri di privacy) sono algoritmi che monitorano questa interazione, permettendo l'esecuzione di una query solo se il budget di privacy residuo non viene superato.

• Composizione Standard: Richiede che i costi di privacy siano fissati in anticipo.
• Composizione Adattiva: Permette di adattare i costi in base ai risultati, ma richiede filtri rigorosi per garantire che il budget totale non venga violato.

Un obiettivo teorico fondamentale è determinare quando un filtro è "gratuito" (free), ovvero quando la composizione adattiva non comporta un costo di privacy aggiuntivo rispetto alla composizione standard (non adattiva). Mentre è noto che la composizione concorrente è gratuita per molte forme di DP, la questione della composizione adattiva "gratuita" per forme di privacy esatte (come i profili di privacy o le distribuzioni della perdita di privacy - PLD) è rimasta aperta.

2. Metodologia e Strumenti Teorici

Gli autori sviluppano una teoria generale basata su diversi strumenti matematici avanzati:

• Distribuzioni della Perdita di Privacy (PLD): Utilizzano le PLD per rappresentare le caratteristiche di privacy di un meccanismo come una distribuzione di probabilità. Le PLD formano un monoide commutativo parzialmente ordinato rispetto all'ordine di Blackwell.
• Ordinamento di Blackwell: Definiscono un ordinamento tra coppie di distribuzioni $(P, Q)$ che rappresenta la difficoltà di distinguere tra due dataset. Questo permette di confrontare rigorosamente i garanzie di privacy.
• Curve Hockey-Stick e Trade-off: Sfruttano le curve di divergenza "hockey-stick" e le curve di trade-off (errore di Tipo I vs Tipo II) per analizzare la composizione. Dimostrano che le PLD possiedono una proprietà di completezza (esiste un supremo per qualsiasi famiglia di PLD).
• Filtri di Residuo (Residue Filters): Introducono una nuova classe di filtri basati su regole di aggiornamento del budget. Un filtro è un "filtro di residuo" se il budget aggiornato $U(B, L)$ soddisfa la condizione: $U(B, L) \oplus L \preceq B$. Questo significa che il budget residuo più il costo della query corrente non supera mai il budget originale.

3. Contributi Chiave

A. Teoria Generale dei Filtri di Residuo

Gli autori dimostrano che i filtri basati su regole di aggiornamento che soddisfano la condizione di residuo sono gratuiti (non introducono costi aggiuntivi).

• Unificazione: Mostrano che i filtri esistenti (DP puro, RDP, zCDP, GDP) sono tutti casi particolari o possono essere espressi come filtri di residuo.
• Nuovo Filtro GDP: Progettano un GDP Residue Filter che migliora rigorosamente il filtro GDP "naïve". Il filtro naïve approssima la query con una distribuzione Gaussiana, sprecando budget. Il filtro di residuo calcola il massimo budget residuo possibile dopo aver sottratto la query esatta, ottenendo risparmi significativi, specialmente quando le query sono mal approssimabili da una Gaussiana o quando il budget è basso.

B. Caratterizzazione dei Filtri Naturali

Il contributo più profondo riguarda i Filtri Naturali, che utilizzano la composizione esatta delle PLD per verificare se il budget totale è rispettato.

• Risultato Principale: I filtri naturali non sono gratuiti in generale.
• Condizione Necessaria e Sufficiente: Un filtro naturale è gratuito per qualsiasi budget se e solo se la famiglia di query ammissibili è totalmente ordinata (total-ordered) rispetto alla composizione e chiusa rispetto alla composizione stessa.
  • Se le query non sono totalmente ordinate (es. query $(\epsilon, \delta)$-DP diverse), l'adattatività può portare a una violazione del budget.
  • Dimostrano che per famiglie di query non ordinate, esiste un avversario adattivo che può forzare una perdita di privacy superiore al budget previsto.

C. Costo dell'Adattatività per $(\epsilon, \delta)$-DP

Poiché i filtri naturali per $(\epsilon, \delta)$-DP non sono gratuiti, gli autori analizzano quanto possono fallire.

• Risultato di Sicurezza: Anche se un filtro naturale basato su $(\epsilon, \delta)$-DP fallisce, non fallisce "troppo male". Dimostrano che l'interazione soddisfa comunque una garanzia $(\chi \cdot \epsilon, \chi \cdot \delta)$-DP.
• Fattore di Blow-up: Il fattore $\chi$ è polilogaritmico rispetto al numero di round di adattatività ($k$) e all'inverso di $\delta$ e $\epsilon$. Questo significa che la violazione è contenuta e gestibile, offrendo una garanzia di sicurezza robusta anche in assenza di gratuità perfetta.

4. Risultati Principali

1. Unificazione: I filtri di residuo catturano tutti i filtri noti e il filtro naturale quando è gratuito.
2. Miglioramento GDP: Il nuovo filtro di residuo per GDP offre risparmi di budget tangibili rispetto all'approccio naïve (fino a $\approx 0.15$ in termini di parametro $\mu$ in alcuni scenari).
3. Impossibilità Generale: I filtri naturali non sono gratuiti per query generiche (come $(\epsilon, \delta)$-DP) a meno che non siano totalmente ordinate. Questo confuta l'ipotesi che l'accounting esatto renda automaticamente gratuita l'adattatività.
4. Condizione di Total Ordering: La proprietà di essere totalmente ordinati è necessaria per avere filtri naturali gratuiti universali.
5. Bound Asintotico: Per i filtri naturali $(\epsilon, \delta)$-DP, il costo dell'adattatività è limitato da un fattore polilogaritmico, garantendo che il sistema rimanga sicuro anche se i parametri peggiorano leggermente.

5. Significato e Implicazioni

• Teorico: Il lavoro risolve una questione aperta sulla natura "gratuita" dell'adattatività nella privacy differenziale. Stabilisce che l'accounting esatto (PLD) non è una panacea per l'adattatività senza condizioni strutturali forti (ordinamento totale).
• Pratico:
  • Suggerisce che per sistemi che richiedono adattatività flessibile, l'uso di filtri basati su residui (come il nuovo GDP residue filter) è preferibile per massimizzare l'utilità.
  • Fornisce rassicurazioni teoriche per l'uso di filtri naturali $(\epsilon, \delta)$-DP: anche se non sono perfetti, il degrado della privacy è limitato e prevedibile.
  • Evidenzia che le famiglie di query come il GDP puro e il $(0, \delta)$-DP sono casi speciali che ammettono filtri gratuiti, mentre le forme più comuni di $(\epsilon, \delta)$-DP no.

In sintesi, il paper fornisce un quadro teorico rigoroso per comprendere i limiti e le opportunità dei filtri di privacy adattivi, introducendo nuovi strumenti (filtri di residuo) e dimostrando che la "gratuità" dell'adattatività dipende criticamente dalla struttura matematica della famiglia di query utilizzata.