Beyond Epsilon: A Principled QIF Framework for Local Differential Privacy

Titolo: Oltre Epsilon: Un Framework QIF Principiato per la Privacy Differenziale Locale

Enunciato del Problema
La Privacy Differenziale Locale (LDP) è diventata lo standard per la raccolta di dati che preservano la privacy nei sistemi su larga scala, in particolare per la stima delle frequenze. Tuttavia, l'attuale panorama per il confronto dei protocolli LDP si basa pesantemente su due approcci limitati:

1. Il parametro $\epsilon$: Questo limita la distinguibilità nel caso peggiore ma non riesce a catturare la reale perdita di informazioni sotto attacchi di inferenza realistici (ad esempio, ricostruzione dei dati o re-identificazione). Due protocolli che soddisfano la stessa garanzia $\epsilon$-LDP possono esibire comportamenti di perdita significativamente diversi.
2. Analisi guidata dall'utilità: I protocolli sono classificati in base all'errore di stima (ad esempio, Errore Quadratico Medio) per un $\epsilon$ fissato. Questa visione dipende dalla metrica e non fornisce un ordinamento principiato della forza della privacy indipendente dalla specifica funzione di utilità.

Di conseguenza, manca un metodo sistematico e indipendente dall'avversario per determinare quando un protocollo LDP è intrinsecamente più privato di un altro.

Metodologia
Gli autori propongono un framework basato sul Flusso Quantitativo di Informazioni (QIF) per analizzare i protocolli di stima delle frequenze LDP. La metodologia centrale coinvolge:

• Modellazione del Canale: Rappresentare i meccanismi LDP come canali probabilistici di teoria dell'informazione definiti da matrici di canale stocastiche per riga ($C_{x,y} = \Pr[Y=y|X=x]$).
• Relazioni di Raffinamento (Ordinamento di Blackwell): Utilizzare il concetto di raffinamento del canale ($B \sqsubseteq A$) per stabilire un ordinamento parziale. Il protocollo $A$ raffina $B$ se $A$ non perde più informazioni di $B$ verso qualsiasi avversario nel caso medio, indipendentemente dalla loro conoscenza a priori o dalla specifica funzione di guadagno. Questo è equivalente a $A$ che è un "offuscamento" di $B$ (cioè $B \cdot W = A$ per qualche canale $W$).
• Connessione alla $f$-Privacy Differenziale: Sfruttare l'equivalenza tra il raffinamento QIF e l'ordinamento delle funzioni di compromesso nella $f$-DP (derivate dal lemma di Neyman-Pearson) per confrontare i meccanismi, in particolare per i canali binari.
• Misure di Vulnerabilità: Analizzare i protocolli utilizzando la capacità di Bayes (massima perdita nel caso medio) e collegare direttamente gli attacchi di ricostruzione dei dati alla vulnerabilità di Bayes sotto una distribuzione uniforme a priori.

Gli autori applicano questo framework a sette protocolli all'avanguardia: Risposta Randomizzata Generalizzata (GRR), Selezione del Sottinsieme (SS), Hashing Locale Binario (BLH), Hashing Locale Ottimizzato (OLH), Codifica Unaria Simmetrica (SUE), Codifica Unaria Ottimizzata (OUE) e Soglia con Codifica Istogramma (THE).

Contributi Chiave

1. Framework QIF Unificato: Il documento fornisce un framework indipendente dalla metrica per confrontare i protocolli LDP tramite matrici di canale e relazioni di raffinamento, consentendo confronti tra avversari e funzioni di utilità diversi.
2. Collegamento tra LDP e QIF: Gli autori dimostrano formalmente che gli attacchi di ricostruzione dei dati studiati nella letteratura precedente coincidono con le nozioni standard QIF di vulnerabilità di Bayes. Nello specifico, il tasso di successo atteso di tali attacchi corrisponde alla capacità di Bayes del canale LDP.
3. Correzione dell'Analisi dell'Hashing Locale: Il documento identifica e corregge un errore nell'analisi attesa degli attacchi di ricostruzione dei dati per i protocolli di Hashing Locale (LH) (in particolare BLH e OLH) riportata in lavori precedenti [8]. Gli autori derivano il corretto rischio di Bayes tramite la vulnerabilità media, fornendo una formula che corrisponde alle valutazioni sperimentali per tutte le dimensioni del dominio, a differenza della precedente approssimazione che falliva per domini piccoli.
4. Analisi del Raffinamento: Lo studio stabilisce relazioni di raffinamento tra i protocolli, rivelando che:
   • Le famiglie GRR, SUE, OUE e THE formano "famiglie di raffinamento" dove vale la monotonia della privacy rispetto a $\epsilon$.
   • OUE e SUE sono incomparabili (né l'uno raffina l'altro) nell'impostazione bit per bit.
   • THE raffina SUE per ogni $\theta$, ma la relazione tra THE e OUE dipende dalla soglia $\theta$ e da $\epsilon$.
   • I protocolli precedentemente considerati "ottimali" basati su metriche di errore sono talvolta strettamente dominati da o incomparabili con altri protocolli quando osservati attraverso la lente della perdita di informazioni.

Risultati

• Validazione Sperimentale: Utilizzando il dataset Kosarak, gli autori hanno corroborato sperimentalmente le relazioni di raffinamento teoriche. Ad esempio, hanno confermato che quando la soglia $\theta$ in THE soddisfa condizioni specifiche rispetto a $\epsilon$, OUE perde più informazioni di THE; altrimenti, la relazione non è di raffinamento.
• Convergenza della Capacità di Bayes: L'analisi delle capacità di Bayes ha rivelato comportamenti di convergenza distinti all'aumentare di $\epsilon$:
  • GRR, SS e THE convergono a $k$ (la dimensione del dominio).
  • SUE converge a un valore leggermente superiore a $k$.
  • BLH converge a 2 (a causa della sua uscita binaria).
  • OLH e OUE convergono approssimativamente a $k/2$.
• Correzione delle Formule LH: La nuova formula per il Tasso di Successo dell'Avversario (ASR) dell'Hashing Locale (Eq. 26) è risultata corrispondere ai risultati sperimentali per ogni $k$ e $\epsilon$, mentre la formula precedente (Eq. 25) si discostava significativamente per piccole dimensioni del dominio.

Significato
Il documento afferma di colmare il divario tra le comunità LDP e dei metodi formali. Spostandosi oltre il singolo parametro $\epsilon$ e le metriche specifiche per l'utilità, l'approccio basato su QIF proposto abilita un "ragionamento principiato e consapevole dell'avversario" sui sistemi localmente privati. Rivela che le classificazioni basate esclusivamente sull'errore di stima possono essere fuorvianti, poiché possono trascurare casi in cui un protocollo è strettamente dominato da un altro in termini di perdita di privacy. Il framework offre un metodo più robusto e completo per valutare la superiorità dei protocolli, assicurando che le garanzie di privacy siano comprese non solo come limiti nel caso peggiore, ma come misure precise del flusso di informazioni contro modelli di minaccia diversi.