A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

Sintesi Tecnica: Un'implementazione a Massima Entropia della Privacy Differenziale sotto Invarianti Lineari

Enunciato del Problema
La privacy differenziale (DP) è lo standard per la riservatezza dei dati, tipicamente implementata aggiungendo rumore Gaussiano o Laplace indipendente alle query del database. Tuttavia, in applicazioni come il Censimento Decennale degli Stati Uniti, determinate query aggregate (ad esempio, i totali della popolazione a livello statale) sono soggette a "invarianti"—vincoli lineari imposti dalla legge o dalla politica che non possono essere perturbati. I meccanismi DP standard, che aggiungono rumore indipendente, violano questi vincoli perché la somma di termini di rumore indipendenti è raramente zero.

Sebbene esistano tecniche di post-elaborazione per forzare gli aggregati a rispettare gli invarianti, tali metodi alterano la distribuzione del rumore, potenzialmente modificando le garanzie di privacy e l'interpretazione del meccanismo DP. Inoltre, proiettare il rumore non vincolato sullo spazio degli invarianti può risultare in una soluzione con entropia inferiore, riducendo l'utilità dei dati rilasciati. La sfida principale consiste nel progettare un meccanismo di aggiunta del rumore che:

1. Mantenga le specifiche distribuzioni marginali (ad esempio, Laplace o Gaussiana) a livello granulare.
2. Soddisfi i vincoli di aggregazione lineare (invarianti) con probabilità uno.
3. Massimizzi l'entropia del vettore di rumore all'interno dello spazio vincolato per garantire che il rumore sia "il più indipendente possibile" date le restrizioni.

Metodologia
Gli autori propongono un meccanismo di Privacy Differenziale con Aggregazione Invariante (AI-DP). L'approccio tratta sia il rumore Gaussiano che quello Laplace come miscele di scala di distribuzioni normali. La metodologia procede in tre fasi principali:

1. Formalizzazione dell'Universo dei Dati Invariante:
   Gli autori ridefiniscono la struttura del database vicino per le garanzie DP. Invece dello standard scambio di singola voce, i database vicini nell'universo invariante ($D_{Q,A,c}$) devono differire in modo da preservare i vincoli lineari $AQ(D) = c$. Questo spesso richiede lo scambio simultaneo di più voci. Le garanzie di privacy vengono quindi valutate all'interno di questo universo vincolato.

2. Costruzione della Matrice di Correlazione tramite POCS:
   Per soddisfare i vincoli $AX = 0$ mantenendo specifiche marginali, il vettore di rumore $X$ è modellato come una normale multivariata $N(0, \Sigma)$ dove $\Sigma = DRD$. Qui, $D$ è una matrice diagonale di scale (derivata dalla distribuzione di miscelazione) e $R$ è una matrice di correlazione che soddisfa $RB = 0$ (dove $B = AD$).
   Trovare un tale $R$ è formulato come un Problema di Fattibilità Convessa (CFP): trovare una matrice nell'intersezione di tre insiemi convessi:

• $C_1$: Il cono delle matrici semidefinite positive.
• $C_2$: Lo spazio affine di matrici con termini diagonali unitari (matrici di correlazione).
• $C_3$: Lo spazio di matrici dove $RB = 0$.
  Gli autori impiegano l'algoritmo di Proiezione Ciclica su Insiemi Convessi (POCS) per trovare una soluzione $R$ in questa intersezione.

3. Ottimizzazione della Massima Entropia:
   La soluzione POCS fornisce una matrice di correlazione valida ma non garantisce la massima entropia. Per soddisfare il requisito della massimizzazione dell'entropia (Requisito [R3]), gli autori formulano un problema di ottimizzazione:
   $$R_{opt} = \min_{R \in C_n} \left[ \text{Tr}(B^T R B) - \tau \log \det(K^T R K) \right]$$
   dove il primo termine impone il vincolo (idealmente zero) e il secondo termine ($\tau$) penalizza la bassa entropia. Questo viene risolto utilizzando un Algoritmo di Gradiente Proiettato.

Contributi Chiave

• Garanzie Teoriche di Privacy: Il documento deriva garanzie di $(\epsilon, \delta)$-DP per il meccanismo proposto sotto l'universo dei dati invariante. Dimostra che il meccanismo soddisfa tali garanzie per database che differiscono per voci che preservano gli invarianti.
• Teoria delle Matrici di Correlazione: Il lavoro contribuisce con nuovi risultati alla letteratura sulle matrici di correlazione, specificamente riguardo allo spazio nullo delle matrici di correlazione.
  • Fornisce una condizione necessaria e sufficiente per l'esistenza di una matrice di correlazione $R$ tale che $RB=0$ per una matrice di vincolo di rango-$k$.
  • Caratterizza l'insieme delle soluzioni come facce dell'ellitopo (l'insieme delle matrici di correlazione) e identifica la soluzione a massimo rango come situata nell'interno relativo di questo insieme.
• Framework Algoritmico: Il documento presenta un algoritmo pratico (Algoritmo 1 e 2) per campionare il rumore da miscele di scale di normali sotto vincoli di uguaglianza lineare, utilizzando POCS e discesa del gradiente proiettata.
• Gestione dei Vincoli Gerarchici: La metodologia si dimostra adattabile a strutture gerarchiche annidate (ad esempio, blocchi $\to$ contee $\to$ stati), garantendo la coerenza attraverso tutti i livelli pur preservando gli invarianti di alto livello.

Risultati

• Illustrazioni Numeriche:
  • Aggregazione Semplice: Per il caso in cui il vettore di vincolo sia un vettore di uno (sommando a un totale), gli autori mostrano che una specifica matrice di correlazione intraclasse (rango $n-1$) è l'unica soluzione a massimo rango e massima entropia, eliminando la necessità di ottimizzazione iterativa in questo caso specifico.
  • Meccanismo Laplace: Rappresentando il rumore Laplace come una miscela di scale gaussiana, gli autori hanno generato con successo 100 campioni di rumore distribuito secondo Laplace soddisfacendo un singolo vincolo lineare. I grafici Q-Q hanno confermato la distribuzione marginale, e le violazioni dei vincoli sono state trascurabili (ordine di $10^{-6}$).
  • Convergenza: L'algoritmo del gradiente proiettato ha dimostrato la convergenza nella minimizzazione della funzione di perdita mantenendo il termine di penalità per l'entropia.
• Probabilità di Violazione: Il documento analizza la probabilità che un vettore di vincolo casuale non sia "bilanciato" (una condizione necessaria per l'esistenza di una matrice di correlazione nullo-correlata). Fornisce un limite superiore (tail bound) che mostra come, per vettori con entrate a coda pesante, la probabilità di infeasibilità sia esponenzialmente piccola.

Significatività e Rivendicazioni
Gli autori sostengono che questo lavoro fornis la via d'accesso corretta per affrontare i vincoli di aggregazione nell'implementazione della DP senza sacrificare l'interpretazione standard della privacy differenziale. Garantendo che il vettore di rumore abbia la massima entropia entro i vincoli, il metodo minimizza la distorsione delle proprietà statistiche dei dati oltre quanto strettamente necessario per soddisfare gli invarianti.

Il documento afferma esplicitamente che contribuisce alla discussione su come analizzare i dati rilasciati e interpretare la semantica della DP in presenza di invarianti, un vuoto identificato nella letteratura sull'implementazione del censimento (Abowd et al., 2022). La metodologia è presentata come dotata di utilità generale oltre i dati del censimento, applicabile a qualsiasi contesto che comporti il campionamento da modelli di miscela normale sotto vincoli di uguaglianza lineare, come i dati di contatori intelligenti (smart-meter) e dispositivi indossabili.

Gli autori rimangono modesti riguardo all'ambito, osservando che l'attuale lavoro si concentra su vincoli di uguaglianza lineare e che sono necessari lavori futuri per affrontare sistemi più generali di vincoli di uguaglianza e disuguaglianza lineare (ad esempio, non negatività). Notano inoltre che la prova teorica riguardante lo spazio nullo delle matrici di correlazione è una soluzione parziale a una questione aperta in quel campo.