Combinatorial Privacy: Private Multi-Party Bitstream Grand Sum by Hiding in Birkhoff Polytopes

1. Problema e Contesto

Il lavoro affronta il problema fondamentale della privacy-preserving aggregation (aggregazione con preservazione della privacy). Nello specifico, $k$ clienti possiedono ciascuno un bitstream privato di lunghezza $n$ e un server desidera calcolare la somma totale di tutti i bit (il numero totale di "1" su $kn$ bit) senza apprendere nulla sui dati individuali di ciascun cliente, né sulle somme parziali.

Le soluzioni esistenti presentano compromessi significativi:

• MPC (Secure Multi-Party Computation): Offre sicurezza composita forte ma con costi di comunicazione e computazione elevati che scalano con la complessità del circuito.
• Homomorphic Encryption (HE): Permette calcoli su dati cifrati ma richiede infrastrutture a chiave pubblica e ha un alto overhead per operazione.
• Differential Privacy (DP): Fornisce garanzie formali aggiungendo rumore, ma sacrifica l'accuratezza (i risultati sono approssimati, non esatti).

L'obiettivo è ottenere risultati esatti, con bassa complessità di comunicazione e sicurezza provabile, senza sacrificare l'accuratezza.

2. Metodologia: Il Protocollo PolyVeil

Il protocollo proposto, chiamato PolyVeil, introduce un nuovo paradigma denominato Combinatorial Privacy (Privacy Combinatoria). L'idea centrale è codificare i dati privati come matrici di permutazione all'interno del Poliedro di Birkhoff (l'insieme delle matrici doppiamente stocastiche).

Meccanismo di Base

1. Codifica: Ogni bit $b \in \{0, 1\}$ viene codificato in una matrice di permutazione $2 \times 2$ ($I_2$ per 0, $J_2$ per 1). Un bitstream di lunghezza $n$ diventa una matrice di permutazione a blocchi diagonali $M(b)$ di dimensione $2n \times 2n$.
2. Mascheramento (Mixing): Il cliente mescola la sua matrice privata $M_t$ con $K_t$ matrici di permutazione casuali (decoy) $P_{t,i}$, pesate da coefficienti casuali $\alpha_{t,i}$.
   $$D_t = \alpha^* M_t + \sum_{i=1}^{K_t} \alpha_{t,i} P_{t,i}$$
   Dove $\alpha^* \in (0,1)$ è un parametro pubblico e $\sum \alpha_{t,i} = 1 - \alpha^*$. Il risultato $D_t$ è una matrice doppiamente stocastica.
3. Estrazione Algebrica: Viene definita una forma bilineare $w^T D_t y$ che estrae la somma dei bit $s_t$ più un termine di rumore $\eta_t$:
   $$f_t = w^T D_t y = \alpha^* s_t + \eta_t$$
4. Aggregazione: I clienti inviano $f_t$ al server e i termini di rumore $\eta_t$ a un "shuffler" (o un aggregatore di rumore separato). Il server calcola la somma totale $S$ sottraendo la somma dei rumori (che è invariante rispetto alla permutazione) e dividendo per $\alpha^*$.

Vulnerabilità Iniziale e Attacco "De-Shuffling"

Il documento identifica una vulnerabilità fatale nelle implementazioni naive: se il server riceve i valori $f_t$ (legati all'identità) e i valori $\eta_t$ (mescolati), può sfruttare il vincolo di integrità (la somma dei bit $s_t$ deve essere un intero tra 0 e $n$) per dedurre quale $\eta_t$ corrisponde a quale $f_t$. Attraverso un attacco di forza bruta sulle permutazioni, il server può recuperare i dati individuali con probabilità 1, rendendo il protocollo insicuro.

Soluzione: Architettura a Due Livelli

Per risolvere questo, gli autori propongono una architettura a due livelli che separa le informazioni:

1. Livello 1 (Server): Riceve solo gli aggregati scalari ($F = \sum f_t$ e $H = \sum \eta_t$). Non vede le matrici $D_t$.
2. Livello 2 (Aggregatore): Riceve le matrici $D_t$ (che contengono la struttura combinatoria) ma non i valori $\eta_t$ né le identità dei clienti.

3. Contributi Chiave e Risultati

A. Sicurezza Teorica del Server (Livello 1)

Il server ottiene sicurezza basata sull'informazione perfetta (statistical distance zero).

• Risultato: Per qualsiasi due configurazioni di input che producono la stessa somma totale $S$, la vista del server è identicamente distribuita.
• Implicazione: Il server non può apprendere nulla sui dati individuali, indipendentemente dalla sua potenza computazionale (sicurezza incondizionata).

B. Sicurezza Computazionale dell'Aggregatore (Livello 2)

L'aggregatore, che vede le matrici $D_t$, deve invertire il processo di mascheramento per trovare la matrice di permutazione originale $M_t$.

• Riduzione a #P-Hard: Gli autori dimostrano che calcolare la densità di probabilità di una matrice doppiamente stocastica casuale (necessaria per un attacco basato sulla verosimiglianza o MAP) richiede di valutare il Permanente di una matrice o il Discriminante Misto.
• Teorema 6.6: Qualsiasi algoritmo che tenti di recuperare $M_t$ calcolando o approssimando il rapporto di verosimiglianza deve risolvere un problema #P-hard.
• Significato: Anche se l'aggregatore ha potenza computazionale illimitata (ma polinomiale), non può estrarre i dati individuali dalle matrici osservate a causa della complessità combinatoria intrinseca della decomposizione del poliedro di Birkhoff.

C. Analisi di Differential Privacy (DP)

Gli autori forniscono un'analisi rigorosa $(\varepsilon, \delta)$-DP per l'aggregatore con costanti esplicite.

• Varianti:
  • Full Variant (Matrici): L'aggregatore vede la matrice completa. La costante di Lipschitz logaritmica cresce come $O(n^4 K_t)$. L'analisi mostra che per avere una garanzia DP non vacua, il rapporto segnale-rumore (SNR) deve essere così basso che il segnale è indistinguibile dal rumore. In questo regime, la DP è tecnicamente vera ma banale.
  • Compressed Variant (Scalare): L'aggregatore vede solo lo scalare $f_t$. L'analisi è univariata. Si trova un punto di equilibrio ottimale (circa $K_t \approx 9$ decoys per $n=100$) dove $\varepsilon \approx 13$ e l'SNR è circa 1. In questo caso, l'aggregatore non può stimare i dati con precisione (l'errore MMSE è molto vicino alla varianza a priori), ma la garanzia DP non è banale.
• Tensione Fondamentale: Esiste un trade-off irrisolto: la sicurezza computazionale (#P-hardness) richiede che l'aggregatore veda la struttura della matrice (dove il segnale è visibile ma difficile da decodificare), mentre la DP non banale richiede che l'aggregatore veda solo uno scalare (dove il segnale è nascosto dal rumore). Non è ancora chiaro se un singolo protocollo possa ottenere entrambe le proprietà simultaneamente.

D. Complessità di Comunicazione

• Versione Completa: $O(kn^2)$ (trasmissione di matrici).
• Versione Compressa: $O(k)$ (trasmissione di scalari), indipendente dalla lunghezza del bitstream $n$.
• Non richiede infrastruttura a chiave pubblica (PKI).

4. Significato e Impatto

Il lavoro introduce la Combinatorial Privacy come un nuovo paradigma distinto da:

1. MPC/HE: Che si basano su difficoltà numeriche (fattorizzazione, LWE). PolyVeil si basa sulla difficoltà combinatoria (#P-hardness) della decomposizione di poliedri.
2. Differential Privacy: Che sacrifica l'accuratezza. PolyVeil produce risultati esatti.

Punti di forza:

• Risultati esatti senza rumore statistico nel output finale.
• Sicurezza incondizionata per il server.
• Sicurezza computazionale basata su problemi #P-hard per l'aggregatore.
• Bassa complessità di comunicazione nella variante compressa.

Limitazioni e Domande Aperte:

• Il gap tra il regime di sicurezza computazionale (dove il segnale è visibile ma hard da decodificare) e il regime di DP non banale (dove il segnale è invisibile) non è stato colto.
• La sicurezza completa dell'aggregatore contro attacchi non basati sulla verosimiglianza (es. metodi spettrali o rilassamenti LP) rimane una congettura (Conjecture 6.5).
• L'attacco di "de-shuffling" dimostra che la semplice separazione dei dati non è sufficiente senza la corretta architettura a due livelli.

In sintesi, PolyVeil offre una soluzione elegante e teoricamente solida per l'aggregazione privata esatta, sfruttando la geometria dei poliedri di Birkhoff per creare barriere computazionali, anche se l'ottimizzazione simultanea della privacy differenziale non banale e della sicurezza computazionale rimane una sfida aperta.