Sintesi Tecnica: Composizione per la Privacy Pufferfish

Problema

La Differential Privacy (DP) è il gold standard per la protezione della privacy, ampiamente implementata dalle grandi organizzazioni grazie alle sue rigorose garanzie e, soprattutto, alle sue proprietà di composizione. La composizione permette di calcolare la perdita di privacy di un sistema complesso come la somma delle perdite dei suoi meccanismi costituenti, consentendo la costruzione di sistemi su larga scala per la preservazione della privacy partendo da componenti più piccoli.

Tuttavia, per dataset con forti correlazioni (ad esempio, i record medici dove lo stato di infezione di una persona influenza gli altri), le semantiche standard della DP possono essere eccessivamente restrittive o prive di significato. La privacy Pufferfish, una definizione basata sull'inferenza/posteriore, affronta questo problema permettendo ai curatori dei dati di specificare un insieme di distribuzioni a priori e coppie di segreti, garantendo che un avversario bayesiano apprenda poco riguardo a segreti specifici. Nonostante i vantaggi semantici per i dati correlati, la Pufferfish è raramente utilizzata in pratica perché manca di garanzie di composizione.

Il documento identifica un difetto critico: è possibile progettare meccanismi Pufferfish che presentano una perdita di privacy nulla quando eseguiti una sola volta, ma che rivelano l'intero dataset quando eseguiti più volte (un fenomeno denominato collasso della privacy). Questa mancanza di composizione rende l'implementazione di piattaforme complesse basate su query Pufferfish intrattabile, poiché ogni nuovo meccanismo richiede un'analisi congiunta manuale e laboriosa di come esso interagisce con tutti gli altri meccanismi supportati.

Metodologia

Gli autori indagano le condizioni necessarie e sufficienti richieste per garantire la composizione lineare per i meccanismi Pufferfish. Il loro approccio si basa su tre pilicoli teorici principali:

1. Dimostrazione del Collasso della Privacy

Il documento costruisce controesempi specifici (Teoremi 1, 2 e 3) mostrando che le definizioni basate sul posteriore, incluse la Pufferfish, non difendono intrinsecamente contro la perdita di privacy tramite composizione.

• Singolo segreto/prior: Un meccanismo può restituire una tupla in cui le componenti dipendono dal segreto in modo tale che, eseguito due volte, permetta a un attaccante di dedurre il vero dataset con alta probabilità, nonostante presenti una perdita nulla in una singola esecuzione.
• Molteplici segreti/prior: Anche con set espansi di segreti o prior, possono essere progettati meccanismi che soddisfano la privacy Pufferfish per una singola esecuzione, ma che falliscono catastroficamente in seguito alla composizione.

2. Condizioni Necessarie (Vincoli NfC)

Gli autori dimostrano che, affinché un insieme di meccanismi Pufferfish compongano linearmente, essi devono soddisfare una classe di vincoli chiamati vincoli NfC (Necessary-for-Composition).

• Questi vincoli prendono la forma di disuguaglianze che coinvolgono combinazioni convesse di log-probabilità delle uscite del meccanismo attraverso diversi dataset.
• Fondamentalmente, il documento prova che affinché questi vincoli siano anche invarianti rispetto al post-processing (una proprietà chiave per l'utilità pratica), essi devono ridurre a disuguaglianze standard della Differential Privacy (DP).
• Intuizione Chiave: Per ottenere la composizione lineare nella Pufferfish, i meccanismi devono essenzialmente soddisfare una forma di differential privacy. Il parametro di privacy Pufferfish $\epsilon_{puffer}$ non può essere garantito di comporre linearmente senza adottare vincoli in stile DP.

3. Condizioni Sufficienti e la Curva di Influenza $a(b)$

Per colmare il divario tra DP e Pufferfish, gli autori introducono la curva di influenza $a(b)$.

• Definizione: Questa curva caratterizza la peggiore perdita di informazione attraverso un insieme di voci di dati a "bassa influenza" ($L$) quando un insieme a "alta influenza" ($H$) di dimensione $b$ è permesso di variare. Essa quantifica quanto un segreto possa influenzare il resto del dataset oltre un gruppo specifico di dimensione $b$.
• Traduzione: Il documento stabilisce una formula di traduzione: se un meccanismo soddisfa la $\epsilon_{DP}$-differential privacy per singola voce, soddisfa la $\epsilon_{puffer}$-Pufferfish privacy dove:
  $$\epsilon_{puffer} = b \cdot \epsilon_{DP} + a(b)$$
  Qui, $b \cdot \epsilon_{DP}$ tiene conto della privacy di gruppo di $b$ voci, e $a(b)$ è la penalità per le correlazioni che si estendono oltre quel gruppo.
• Composizione: Gli autori dimostrano che se i meccanismi sono costruiti utilizzando questa traduzione, i loro parametri Pufferfish compongono linearmente (specificamente, in modo sub-additivo). La "penalità" $a(b)$ viene pagata una sola volta, non per ogni meccanismo, permettendo una migliore utilità rispetto alla semplice addizione.

Contributi Chiave

1. Prova del Collasso della Privacy: Il documento dimostra rigorosamente che le definizioni di privacy basate sul posteriore (come la Pufferfish) non sono robuste alla composizione senza vincoli aggiuntivi, mostrando meccanismi che sono sicuri in isolamento ma che falliscono completamente quando composti.
2. Condizioni Necessarie e Sufficienti: Gli autori provano che la composizione lineare nella Pufferfish necessita dell'inclusione di vincoli in stile differential privacy (vincoli NfC). Dimostrano che solo i vincoli in stile DP sono invarianti rispetto al post-processing all'interno di questo framework.
3. Framework della Curva di Influenza $a(b)$: Introducono un framework generale per tradurre qualsiasi esistente meccanismo DP in un meccanismo Pufferfish composibile. Questo generalizza il lavoro precedente (ad esempio, il Markov Quilt Mechanism di Song et al.) che era limitato al rumore di Laplace e a specifici prior di reti di Markov.
4. Robustezza all'Incertezza del Prior: Il framework include metodi per gestire l'incertezza dei prior mis-specificati, permettendo ai curatori di calcolare limiti superiori sulla curva di influenza anche quando la vera distribuzione dei dati è incerta (ad esempio, entro un margine di errore del 20%).

Risultati Sperimentali

Gli autori valutano il loro framework (denominato Ours-Exp) rispetto allo stato dell'arte rappresentato dal Markov Quilt Mechanism (MQM) su due dataset reali con forti correlazioni temporali:

• Dataset Foursquare Check-in: Dati di localizzazione con alta correlazione tra utenti.
• Dataset Capture24: Dati di monitoraggio dell'attività nelle 24 ore.

Risultati:

• Utilità Superiore: Il framework proposto supera significativamente il MQM in tutti i parametri di privacy ($\epsilon_{puffer}$) e metriche (Accuracy@k, Hit Rate, NDCG, $\ell_1$ Count Error).
• Flessibilità del Meccanismo: Il miglioramento deriva dalla capacità del framework di adattare l'Exponential Mechanism (che è ottimale per le query Top-$k$) all'ambiente Pufferfish. Il MQM è limitato al meccanismo di Laplace, che è meno adatto per le query di ranking.
• Robustezza: L'incorporazione del 20% di incertezza del prior nel calcolo della curva di influenza ha comportato solo una modesta diminuzione dell'utilità, dimostrando la fattibilità pratica del framework anche con una conoscenza imperfetta del prior.

Significato e Rivendicazioni

Il documento sostiene di aver risolto un importante collo di bottiglia che ostacola lo sviluppo di piattaforme di risposta alle query basate su Pufferfish. Provando che i meccanismi Pufferfish composibili devono intrinsecamente soddisfare i vincoli della differential privacy, gli autori sostengono che la strada da seguire non è inventare nuovi e complessi meccanismi specifici per la Pufferfish, ma sfruttare la vasta libreria di meccanismi DP esistenti.

Il significato di questo lavoro risiede nel:

• Unificazione: Collega formalmente la Pufferfish e la Differential Privacy, mostrando che per ottenere semantiche interpretabili per i dati correlati e i benefici della composizione, è necessario adottare i meccanismi DP.
• Praticità: Fornisce una "ricetta" per i progettisti di sistemi: calcolare la curva di influenza $a(b)$ per i propri dati e segreti, e poi semplicemente scalare il budget di privacy di qualsiasi algoritmo DP per ottenere una garanzia Pufferfish composibile.
• Generalizzazione: Va oltre i limiti del lavoro precedente (che era limitato al rumore di Laplace e alle reti di Markov) per supportare dataset tabulari generali e prior arbitrari.

Gli autori concludono che i loro risultati teorici implicano che la progettazione di nuovi meccanismi per la Pufferfish debba essere fatta costruendo sui piani esistenti di DP, rendendo di fatto l'adattamento della DP alla Pufferfish un processo inevitabile e sistematico piuttosto che euristico.