Defense against Poisoning Attacks under Shuffle-DP

1. Enunciato del Problema

Il paper affronta una vulnerabilità critica nel modello Shuffle Differential Privacy (Shuffle-DP). Sebbene Shuffle-DP offra un equilibrio superiore tra privacy e utilità rispetto alla Local-DP (utilizzando un mescolatore fidato per anonimizzare i messaggi), i protocolli esistenti si basano su un'assunzione forte: tutti gli utenti sono onesti.

In scenari reali, si verificano attacchi di avvelenamento quando utenti avversari (utenti corrotti) manipolano il protocollo per:

1. Violare la Privacy: Omettendo la generazione del rumore, riducendo efficacemente il budget di privacy collettivo.
2. Distruggere l'Utilità: Iniettando messaggi eccessivi (attacchi di inondazione) o manipolando gli input per distorcere i risultati dell'aggregazione.

Le difese esistenti sono limitate. Alcune rilevano solo gli attacchi senza recuperare i risultati (portando a una perdita totale di utilità), mentre altre sono limitate a compiti specifici (come la stima della frequenza con conteggi di messaggi fissi) e non possono generalizzarsi a query comuni come la somma o il conteggio di bit. La sfida principale è progettare un framework generale che difenda contro gli attacchi di avvelenamento per query che preservano l'unione, mantenendo al contempo alta utilità ed efficienza nelle comunicazioni.

2. Metodologia

Gli autori propongono un framework di difesa generale basato su una struttura gerarchica che trasforma qualsiasi protocollo Shuffle-DP esistente in una versione robusta. La metodologia evolve attraverso tre stadi:

A. Soluzione Strawman: Shuffle-DP a Singolo Utente (SUSDP)

• Concetto: Ogni utente è assegnato a un mescolatore dedicato. L'analizzatore verifica la ragionevolezza delle singole uscite.
• Limitazione: Sebbene rilevi gli attacchi, degrada alle prestazioni della Local-DP, risultando in un errore di $O(n)$, inaccettabile per dataset di grandi dimensioni.

B. Block Shuffle-DP (BSDP)

• Concetto: Gli utenti sono partizionati in blocchi di dimensione $\sqrt{n}$. Il protocollo opera su tre livelli: livello Utente, livello Blocco e livello Output.
• Meccanismo:
  • Rilevamento: L'analizzatore confronta l'output aggregato di un blocco con la somma delle singole uscite dei suoi membri. Se la deviazione supera una soglia, il blocco viene segnalato.
  • Recupero: Se un blocco viene segnalato, il suo risultato viene ricostruito sommando le singole uscite valide dei suoi membri.
• Risultato: Riduce l'errore a $O(\sqrt{n})$, un miglioramento significativo rispetto a SUSDP ma ancora subottimale.

C. Shuffle-DP Gerarchico (HSDP) e HSDP Ottimizzato (OHSDP)

• Concetto: Gli utenti sono organizzati in un albero binario. Le foglie sono singoli utenti; i nodi interni rappresentano gruppi formati fondendo due sottogruppi.
• Meccanismo:
  • Verifica Gerarchica: L'analizzatore verifica la coerenza dal basso verso l'alto. Per qualsiasi nodo, verifica se l'output del nodo corrisponde alla somma degli output dei suoi figli.
  • Recupero: Se un nodo viene segnalato come avvelenato, il suo valore viene sostituito dalla somma dei risultati validi dei suoi figli. Questo recupero ricorsivo isola l'impatto dell'attaccante su un percorso logaritmico nell'albero.
  • Ottimizzazione (OHSDP): Per ridurre i costi di comunicazione, i gruppi del livello inferiore vengono aumentati da dimensione 1 a $\lambda = \log n \cdot \log(1/\delta)$. Questo riduce il numero di livelli mantenendo il limite di errore polilogaritmico.
• Estensione a Multi-Attaccanti: Il framework è esteso per gestire $k$ attaccanti assicurando che le dimensioni dei gruppi siano sufficientemente grandi da mantenere una maggioranza di utenti onesti, scalando l'errore di un fattore $k$.

3. Contributi Chiave

1. Primo Framework di Difesa Generale: Il paper presenta il primo framework capace di difendere qualsiasi query che preservi l'unione (es. conteggio di bit, somma, stima della frequenza, conteggio di intervalli) dagli attacchi di avvelenamento nel modello Shuffle-DP.
2. Robustezza con Alta Utilità:
   • Senza Attacchi: Il framework preserva un errore asintoticamente equivalente al protocollo Shuffle-DP originale.
   • Con Attacchi: In presenza di un numero costante di attaccanti, l'errore aumenta solo di un fattore polilogaritmico ($O(\log^2 n)$), piuttosto che di fattori lineari o di radice quadrata.
3. Efficienza nelle Comunicazioni: Il framework comporta solo un aumento polilogaritmico del costo di comunicazione (messaggi e bit per utente) rispetto al protocollo base.
4. Garanzie Teoriche: Sono fornite prove formali per la $(\epsilon, \delta)$-differential privacy e i limiti di errore sia in scenari con singolo che con multipli attaccanti.

4. Risultati Sperimentali

Gli autori hanno valutato il loro framework (OHSDP) su tre query fondamentali: Conteggio di Bit, Somma e Stima della Frequenza, utilizzando sia dataset sintetici che reali (es. Adult, SF-Salary).

• Utilità sotto Attacco:
  • I protocolli all'avanguardia (SOTA) senza difesa hanno subito un errore relativo >100% (fallimento totale) quando un singolo utente ha lanciato un attacco di avvelenamento.
  • Il framework proposto ha rilevato e mitigato con successo gli attacchi, recuperando i risultati con errori relativi < 1%.
  • L'aumento dell'errore dovuto alla difesa (senza attacco vs con attacco) è stato circa $(\log n)^2$, confermando i limiti teorici.
• Sovraccarico di Comunicazione:
  • Il framework ha aumentato il numero di messaggi per utente di un fattore $O(\log n)$ rispetto ai protocolli base come BBGN o LWY.
  • La dimensione del messaggio è aumentata di $O(\log n)$ bit (per gli identificatori del mescolatore).
• Confronto tra Protocolli:
  • SUSDP: Errore $\propto O(n)$ (Troppo alto).
  • BSDP: Errore $\propto O(n^{1/4})$ (Meglio, ma ancora alto).
  • OHSDP: Errore $\propto O(\log^2 n)$ (Ottimale).
• Sensibilità ai Parametri: Gli esperimenti hanno mostrato che la regolazione della dimensione del gruppo del livello inferiore ($\lambda$) consente un compromesso tra utilità e costo di comunicazione, con impostazioni ottimali identificate per diverse dimensioni di dataset.

5. Significato

Questo lavoro è significativo perché colma un divario critico nel deployment di Shuffle-DP. Dimostrando che è possibile una difesa generale e robusta contro gli attacchi di avvelenamento senza sacrificare i vantaggi di utilità di Shuffle-DP, il paper abilita l'applicazione pratica di questi protocolli in ambienti avversari (es. raccolta dati decentralizzata, reti IoT). Sposta il campo dall'"assumere utenti onesti" all'"assumere utenti maliziosi ma recuperare l'utilità", rendendo Shuffle-DP uno standard aureo praticabile per l'analisi della privacy nel mondo reale.