Multi-user Pufferfish Privacy

Titolo: Multi-user Pufferfish Privacy (Privacy Pufferfish Multi-utente)

1. Il Problema

Il lavoro affronta la sfida di garantire l'indistinguibilità individuale in un sistema multi-utente che risponde a query aggregate, utilizzando il framework della Privacy Pufferfish.
A differenza della Privacy Differenziale (DP) classica, che assume dati deterministici (ogni individuo riporta sempre lo stesso valore), questo studio considera scenari in cui i dati degli utenti sono intrinsecamente randomizzati (variabili aleatorie). Gli scenari specifici analizzati includono:

1. Un utente cambia il valore riportato nella query.
2. Un utente lascia il sistema (assenza/presenza).
3. Un utente viene sostituito da un altro con caratteristiche statistiche (distribuzioni di probabilità) diverse.

L'obiettivo è calibrare il rumore aggiunto alla risposta della query in modo che un avversario non possa distinguere tra questi diversi scenari, proteggendo così la privacy individuale anche in presenza di variabilità intrinseca dei dati e di probabilità di presenza degli utenti.

2. Metodologia

Gli autori adottano il meccanismo di Laplace (aggiunta di rumore Laplaciano alla risposta della query) e lo calibrano utilizzando il metodo Kantorovich, basato sulla metrica di Wasserstein di ordine 1 ($W_1$).

• Modello di Sistema: Si considera un database $D$ composto da $|V|$ utenti, dove ogni utente $i$ contribuisce con una variabile aleatoria $D_i$. La query è una somma aggregata $X = \sum D_i$. Ogni utente ha una probabilità di presenza $\zeta_i$.
• Coppie di Segreti: Il framework Pufferfish definisce coppie di segreti $(s_i, s_j)$ tra cui garantire l'indistinguibilità. Il paper analizza quattro insiemi di coppie:
  • $S_{a,b}$: Indistinguibilità tra due valori specifici ($a$ e $b$) riportati dallo stesso utente.
  • $S_{a,\perp}$: Indistinguibilità tra la presenza di un utente che riporta un valore $a$ e la sua assenza.
  • $S_{P,\perp}$: Indistinguibilità tra la presenza di un utente con una specifica distribuzione di probabilità $P_i$ e la sua assenza.
  • $S_{P,Q}$: Indistinguibilità tra la presenza di un utente con distribuzione $P_i$ e la presenza di un utente con distribuzione $Q_i$.
• Calibrazione del Rumore: Invece di calcolare la sensibilità classica $L_1$, gli autori utilizzano la distanza di Wasserstein tra le distribuzioni condizionate dei dati pubblici dati i segreti. La scala del rumore $\theta$ è determinata dalla massima distanza di trasporto ottimale tra le distribuzioni dei segreti.

3. Contributi Chiave

I principali contributi teorici e pratici del lavoro sono:

1. Condizioni Sufficienti Indipendenti dal Contesto: È stato dimostrato che per garantire la privacy Pufferfish su un utente specifico, le condizioni sufficienti per la calibrazione del rumore dipendono solo dalle statistiche di quell'utente e non dalle statistiche degli altri utenti nel sistema o dalle loro probabilità di presenza ($\zeta_i$). Questo semplifica notevolmente l'implementazione in sistemi dinamici.
2. Derivazione per Scenari Complessi:
   • Per le coppie di valori fissi ($S_{a,b}$) e presenza/assenza con valore fisso ($S_{a,\perp}$), la scala del rumore è proporzionale alla differenza assoluta dei valori ($|a-b|$ o $|a|$).
   • Per le coppie basate su distribuzioni ($S_{P,\perp}$ e $S_{P,Q}$), sono state derivate condizioni basate sulle funzioni di distribuzione cumulativa (CDF) e sui momenti delle variabili aleatorie.
3. Ottimizzazione per Variabili Bernoulliane: Per variabili aleatorie binarie (distribuzione di Bernoulli), gli autori hanno derivato condizioni sufficienti rilassate. Queste condizioni permettono di ridurre la quantità di rumore necessaria rispetto alle condizioni conservative, migliorando l'utilità dei dati senza compromettere la privacy.
4. Metodo Computazionale Efficiente: L'uso dell'approccio di Kantorovich ($W_1$) evita i problemi computazionali associati alla metrica $W_\infty$, permettendo di calcolare la scala del rumore direttamente dalle distribuzioni a priori senza dover risolvere problemi di ottimizzazione complessi per ogni query.

4. Risultati Sperimentali

Gli autori hanno validato i risultati teorici su tre dataset reali del repository UCI Machine Learning: Adult, Bank Marketing e Student Performance.

• Riduzione del Rumore: Gli esperimenti hanno mostrato che l'uso delle condizioni rilassate (specialmente per variabili binarie e distribuzioni $S_{P,Q}$) riduce significativamente il parametro di scala $\theta$ rispetto alle condizioni conservative (basate sul massimo valore assoluto).
• Utilità dei Dati: La riduzione del rumore si traduce in una maggiore utilità dei dati aggregati. Ad esempio, nel dataset Adult, la differenza tra la scala del rumore calcolata con la condizione conservativa e quella rilassata è stata marcata, permettendo una privacy forte con meno degradazione della qualità dell'analisi.
• Robustezza: I risultati confermano che la privacy Pufferfish può proteggere efficacemente contro inferenze di appartenenza (membership inference) quando vengono aggiunti, rimossi o modificati interi gruppi di utenti (classi di dati) nel dataset.

5. Significato e Impatto

Questo lavoro è significativo per diversi motivi:

• Generalizzazione della Privacy Differenziale: Estende i concetti di privacy a scenari realistici dove i dati non sono statici ma probabilistici, colmando il divario tra la teoria della privacy differenziale e applicazioni come l'apprendimento federato e l'analisi aggregata locale.
• Indipendenza dal Sistema: La scoperta che la calibrazione del rumore per un utente è indipendente dagli altri utenti è un risultato fondamentale per la scalabilità dei sistemi multi-utente.
• Efficienza e Utilità: Dimostra che è possibile ottenere garanzie di privacy rigorose (indistinguibilità statistica) riducendo il rumore necessario, rendendo la privacy Pufferfish più pratica e meno costosa in termini di utilità dei dati rispetto alle approcci conservativi precedenti.
• Applicabilità: Offre un framework matematico solido per proteggere la privacy in contesti dove la presenza degli utenti è incerta e i loro dati variano secondo distribuzioni di probabilità note o stimate.

In sintesi, il paper fornisce un metodo rigoroso ed efficiente per calibrare il rumore in sistemi multi-utente probabilistici, garantendo che le statistiche aggregate non rivelino informazioni sensibili su singoli individui o gruppi specifici, anche in scenari dinamici di presenza/assenza.