Sintesi Tecnica: Differenziale di Metrica della Privacy a Livello Utente tramite la Earth Mover's Distance

Definizione del Problema

La Privacy Differenziale (DP) è diventata lo standard per l'analisi dei dati, offrendo tradizionalmente garanzie di privacy uniformi dove ogni coppia di dataset di input è trattata con la stessa sensibilità. Tuttavia, in molte applicazioni pratiche, i dati presentano eterogeneità; ad esempio, rivelare la città esatta di residenza di un utente è più sensibile che rivelare il suo paese. La Metric Differential Privacy (Metric DP) affronta questo problema degradando la garanzia di privacy linearmente con la distanza tra le coppie di input, permettendo una migliore utilità quando gli input sono simili.

Mentre il lavoro precedente sulla Metric DP si è concentrato sul setting item-level (dove ogni utente contribuisce con un singolo elemento di dato), gli scenari reali spesso coinvolgono contributi user-level, dove un singolo utente fornisce una collezione di elementi (ad esempio, una cronologia di posizioni o un insieme di parole). Gli esistenti framework di user-level DP si affidano alla standard DP, trattando tutti i cambiamenti al dataset di un utente come ugualmente sensibili, indipendentemente dall'entità o dalla natura del cambiamento. Questo articolo avvia lo studio della Metric DP a livello utente, utilizzando specificamente la Earth Mover's Distance (dEM) come metrica sottostante. L'obiettivo è definire una nozione di privacy in cui la sensibilità del contributo di un utente dipenda sia dalla frazione di dati modificati che dalla distanza di tali cambiamenti, catturando una semantica di privacy più sfumata rispetto alla standard user-level DP.

Metodologia

1. Definizione di dEM-DP

Gli autori definiscono la dEM-DP misurando la distanza tra due dataset di utenti $K$ e $K'$ utilizzando la Earth Mover's Distance (nota anche come distanza 1-Wasserstein).

• Metrica: $d_{EM}(\tilde{K}, \tilde{K}')$ rappresenta il costo minimo per trasportare la distribuzione di probabilità del dataset $K$ verso $K'$, dove il costo è la quantità di dati spostati moltiplicata per la distanza $d_X$ tra gli elementi.
• Garanzia di Privacy: Un meccanismo $M$ soddisfa la $(\alpha, \delta)$-bounded dEM-DP per ogni coppia di dataset $K, K'$ della stessa dimensione:
  $$\Pr[M(K) \in O] \le e^{\alpha \cdot d_{EM}(\tilde{K}, \tilde{K}')} \Pr[M(K') \in O] + \delta$$
  Qui, il parametro di privacy scala con la distanza. Se $d_{EM}$ è piccolo (dataset simili), la garanzia di privacy è più forte ( $\epsilon$ effettivo inferiore) rispetto alla standard DP, che applicherebbe un $\epsilon$ uniforme.

2. Design del Meccanismo

Il paper propone due nuovi meccanismi per rilasciare query sotto dEM-DP sia nel Modello Locale (gli utenti privatizzano i dati prima dell'invio) sia nel Modello Centrale (un aggregatore fidato detiene i dati).

A. Query Lineari (PrivEMDLinear)

Per query lineari della forma $F\tilde{K}$, gli autori analizzano la sensibilità sotto dEM.

• Analisi della Sensibilità: A differenza della standard DP che richiede che la funzione di query sia limitata, l'analisi dEM-DP richiede che la funzione $f$ (che rappresenta la query) sia Lipschitz continua.
• Risultato: Gli autori dimostrano che la sensibilità di una query lineare sotto dEM è limitata superiormente dalla costante di Lipschitz della funzione di query. Ciò consente l'aggiunta di rumore calibrato (ad esempio, usando il meccanismo K-norm o il meccanismo Gaussiano) che è proporzionale alla costante di Lipschitz piuttosto che a un limite globale peggiore, migliorando l'utilità.

B. Query per Elementi Non Ordinati (PrivEMDItemWise)

Per il rilascio di un insieme di output rumorosi per ogni elemento nel dataset di un utente (ad esempio, un istogramma), il meccanismo applica un meccanismo base di item-level metric DP $A$ a ciascun elemento e poi mescola (shuffles) i risultati.

• Amplificazione della Privacy tramite Shuffling: Gli autori generalizzano il risultato della "privacy amplification by shuffling" al setting di metric DP. Poiché l'output è una lista non ordinata, un avversario non può collegare output specifici a specifici indici di input.
• Novità Tecnica: Dimostrano che lo shuffling di $m$ elementi riduce il costo di privacy da $O(m\alpha)$ (tramite composizione) a $O(\alpha\sqrt{m})$. Questo risultato è derivato dall'analisi del coupling tra i vettori di input e dallo sfruttamento delle proprietà del modello di shuffling.

3. Estensione a Dati Unbounded (Non Limitati)

I dataset reali spesso hanno dimensioni variabili per utente (setting unbounded), il che complica l'analisi dEM poiché la dimensione stessa del dataset diventa una preoccupazione per la privacy.

• Riduzione: Gli autori propongono una riduzione black-box da unbounded a bounded dEM-DP.
• Meccanismo: Utilizzano il campionamento con sostituzione per proiettare qualsiasi dataset di utente su una dimensione fissa $s$. Dimostrano che questa proiezione è "smooth", ovvero la distanza dEM tra i dataset proiettati è vicina alla distanza dEM tra i dataset originali (fino a un piccolo fattore additivo).
• dEM-DP Discreta: Per gestire l'errore additivo dal campionamento, introducono una definizione "discreta" di dEM-DP dove i cambiamenti con distanza $\le r$ sono protetti uniformemente. Dimostrano che per dimensioni di campione sufficientemente grandi, la unbounded dEM-DP può essere ridotta alla bounded dEM-DP con una perdita trascurabile nella semantica di privacy.

Contributi Chiave

1. Definizione di User-Level Metric DP: Il paper stabilisce una definizione formale di Metric DP a livello utente utilizzando la Earth Mover's Distance, catturando sia gli aspetti spaziali che quelli di entità dei cambiamenti nei dati.
2. Nuovi Meccanismi:
   • PrivEMDLinear: Un meccanismo per query lineari che sfrutta la continuità di Lipschitz per limitare la sensibilità, offrendo una migliore utilità rispetto alla standard user-level DP per specifici tipi di query.
   • PrivEMDItemWise: Un meccanismo generale per query item-wise che utilizza lo shuffling. Gli autori forniscono un'analisi di amplificazione della privacy generalizzata che mostra un miglioramento di $\sqrt{m}$ rispetto ai limiti di composizione standard.
3. Riduzione Unbounded: Una tecnica di riduzione black-box che converte i meccanismi bounded dEM-DP in meccanismi unbounded tramite campionamento, consentendo l'applicazione di questi meccanismi a dataset con dimensioni variabili di contributo dell'utente.
4. Miglioramenti dell'Utilità: L'analisi teorica dimostra che i meccanismi dEM-DP possono ottenere un'utilità strettamente migliore (minor errore) rispetto alle baseline standard di user-level DP per:
   • Query di Embedding Lineare: Sia nel modello centrale che in quello locale, particolarmente quando il parametro di privacy $\alpha$ può essere maggiore della $\epsilon$ standard per input dissimili.
   • Stima delle Frequenze: Nel modello locale, l'errore è migliorato quando la dimensione del dominio e i parametri di privacy soddisfano specifiche condizioni, sfruttando il fatto che solo gli elementi "vicini" (all'interno di cluster) richiedono una forte privacy.

Risultati e Significatività

Il paper sostiene che la dEM-DP offre una definizione di privacy più fine che si allinea meglio con le sematiche di privacy del mondo reale.

• Semantica della Privacy: Nella standard DP, cambiare i dati di un utente per un intero mese è trattato con la stessa sensibilità di cambiare un singolo giorno. Nella dEM-DP, il cambiamento di un singolo giorno è considerato meno sensibile (minore $d_{EM}$), permettendo meno rumore e maggiore utilità, mentre un cambiamento di un mese riceve una garanzia più forte.
• Guadagni di Utilità: I limiti teorici mostrano che i meccanismi dEM-DP possono superare la standard user-level DP per quanto riguarda la stima delle frequenze, l'errore dipende dal dominio $k$ e dal parametro di privacy è migliorato sotto dEM-DP quando i dati presentano una struttura (ad esempio, metriche clusterizzate).
• Generalizzabilità: La riduzione al setting bounded e l'analisi dello shuffling suggeriscono che queste tecniche possono essere applicate ampiamente a vari spazi metrici e tipi di query oltre agli esempi specifici (posizione, testo, grafi) forniti.

Gli autori posizionano questo lavoro come il primo a proporre una definizione generale di user-level Metric DP tramite dEM, andando oltre le specifiche applicazioni testuali per un framework applicabile a spazi metrici generali. Enfatizzano che, sebbene la dEM-DP sia una rilassazione della standard DP, essa fornisce un compromesso più pratico per le applicazioni in cui la somiglianza dei dati correla con la sensibilità.