Aggregazione Sicura Multi-Messaggio con Privacy della Domanda

Informazioni Fondamentali

• ID Articolo: 2504.20639
• Titolo: Multi-Message Secure Aggregation with Demand Privacy
• Autori: Chenyi Sun, Ziting Zhang, Kai Wan (Huazhong University of Science and Technology), Giuseppe Caire (Technische Universität Berlin)
• Classificazione: cs.IT math.IT
• Data di Pubblicazione: 13 ottobre 2025 (arXiv v2)
• Link Articolo: https://arxiv.org/abs/2504.20639

Riassunto

Questo articolo affronta il problema dell'aggregazione sicura multi-messaggio con privacy della domanda, dove un server mira a calcolare Kc≥1 combinazioni lineari degli input locali provenienti da K utenti distribuiti. Il problema risolve due compiti: (1) sicurezza, garantendo che il server ottenga solo le combinazioni lineari desiderate senza rivelare altre informazioni sugli input degli utenti; (2) privacy, impedendo agli utenti di conoscere i compiti computazionali del server. Inoltre, viene considerato l'impatto dell'abbandono degli utenti, dove fino a K-U utenti possono disconnettersi con identità non prevedibili in anticipo. Gli autori propongono due schemi distinti per i casi Kc=1 e 2≤Kc<U. Per Kc=1, introducono un metodo che utilizza variabili casuali per la crittografia moltiplicativa della domanda del server; per 2≤Kc<U, utilizzano il calcolo privato simmetrico robusto per recuperare combinazioni lineari di chiavi nel secondo round.

Contesto di Ricerca e Motivazione

Definizione del Problema

L'apprendimento federato consente agli utenti distribuiti di collaborare nell'addestramento di un modello globale sotto il coordinamento di un server centrale, ma gli aggiornamenti del modello potrebbero comunque rivelare informazioni sui dati locali degli utenti. Per migliorare ulteriormente la sicurezza, l'aggregazione sicura è stata introdotta per garantire che il server ottenga solo gli aggiornamenti aggregati senza alcuna informazione aggiuntiva sui dati degli utenti.

Motivazione della Ricerca

1. Esigenze di Apprendimento Multi-Compito: Rispetto all'apprendimento a singolo compito, l'apprendimento multi-compito può sfruttare più risultati per migliorare le prestazioni complessive dell'addestramento del modello, aumentando l'efficienza di apprendimento attraverso la condivisione di informazioni e risorse.
2. Limitazioni dei Metodi Esistenti:
   • I problemi di aggregazione sicura con sicurezza teorica dell'informazione esistenti si concentrano principalmente sul caso Kc=1
   • Manca la considerazione della protezione della privacy dei compiti computazionali del server
   • È necessario garantire sicurezza e privacy in caso di abbandono degli utenti
3. Esigenze di Applicazioni Pratiche: Negli scenari di apprendimento federato reali, il server potrebbe aver bisogno di calcolare più combinazioni lineari diverse, mentre gli utenti non dovrebbero conoscere le specifiche esigenze computazionali del server.

Contributi Principali

1. Formalizzazione di un Nuovo Problema: Propone per la prima volta il problema dell'aggregazione sicura multi-messaggio con privacy della domanda, estendendo l'ambito della ricerca tradizionale sull'aggregazione sicura.
2. Schema Ottimale (Kc=1): Propone uno schema di aggregazione sicura che combina la crittografia moltiplicativa della domanda e la crittografia additiva del modello, realizzando la regione di velocità di comunicazione ottimale, equivalente alla capacità del problema di aggregazione sicura senza vincoli di privacy.
3. Schema Quasi-Ottimale (2≤Kc<U): Utilizzando schemi di calcolo privato simmetrico, migliora significativamente il metodo baseline di ripetizione diretta dello schema precedente Kc volte, con velocità ottimale nel primo round e velocità entro un fattore 2 dall'ottimalità nel secondo round.
4. Analisi Teorica: Fornisce prove complete di raggiungibilità e analisi di limiti inversi, stabilendo le fondamenta teoriche del problema.

Dettagli dei Metodi

Modello di Sistema

Partecipanti:

• 1 server e K utenti non collusivi (K≥2)
• L'utente i possiede il vettore di input Wi e la chiave Pi
• Wi contiene L simboli indipendenti e identicamente distribuiti uniformemente, definiti sul campo finito Fq

Funzione Obiettivo: Il server calcola la mappa lineare: $g(W_1, \cdots, W_K) = F[W_1, \cdots, W_K]^T$

dove F è una matrice di coefficienti di dimensione Kc×K: $F = \begin{pmatrix} a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}$

Modello di Comunicazione:

• Primo Round: Il server invia la query Q1,i all'utente i, l'utente i risponde con il messaggio Xi
• Secondo Round: Il server comunica l'insieme degli utenti attivi U1, invia la query Q^{U1}_{2,i}, l'utente i invia Y^{U1}_i

Vincoli

1. Decodificabilità: Il server può calcolare senza errori le combinazioni lineari desiderate
2. Sicurezza: Il server non può ottenere informazioni sugli input degli utenti oltre il risultato del calcolo target
3. Privacy: Gli utenti non possono dedurre la matrice di domanda F del server

Schema per il Caso Kc=1

Idea Centrale

Combina la crittografia moltiplicativa della domanda e la crittografia additiva del modello, crittografando la domanda del server attraverso una variabile casuale t.

Passaggi Dettagliati

Fase 1 (Generazione della Query):

• Il server seleziona casualmente t ∈ Fq{0}
• Definisce la query: $Q_{1,i} = \frac{1}{ta_{1,i}}$, i ∈ K

Fase 2 (Generazione della Chiave):

• Genera Zi per ogni utente i, uniformemente distribuito su F^L_q
• Divide Zi in U sotto-chiavi: Zim ∈ F^{L/U}_q
• Codifica utilizzando una matrice MDS M: $[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}$

Fase 3 (Trasmissione del Primo Round):

• L'utente i invia: $X_i = W_i + Q_{1,i}Z_i$

Fase 4 (Trasmissione del Secondo Round):

• L'utente j ∈ U1 invia sotto-chiavi codificate aggregate: $\sum_{i \in U_1}[\tilde{Z}_i]_j$
• Il server recupera $\sum_{i \in U_1} Z_i$ attraverso decodifica MDS

Processo di Decrittazione

Il server calcola: $\sum_{i \in U_1} \frac{1}{Q_{1,i}}X_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i + \sum_{i \in U_1} Z_i$

Poiché $t \sum_{i \in U_1} a_{1,i}W_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i$, il server può decodificare la combinazione lineare target.

Schema per il Caso 2≤Kc<U

Idea Centrale

Utilizza il calcolo privato simmetrico robusto per garantire sicurezza e privacy nella trasmissione del secondo round.

Passaggi Dettagliati

Fase 1 (Generazione della Chiave):

• Per ogni i ∈ K, seleziona casualmente Zi da F^L_q
• Tutti gli utenti condividono la chiave: Pi = (Zi)i∈K
• Condivide L/(U-1) variabili casuali pubbliche come maschere di chiave

Fase 2 (Trasmissione del Primo Round):

• L'utente i invia: $X_i = W_i + Z_i$

Fase 3 (Trasmissione del Secondo Round):

• Il server deve recuperare Kc combinazioni di chiavi: $\sum_{i \in U_1} a_{n,i}Z_i$, n ∈ Kc
• Divide ogni chiave Zi in sotto-chiavi di lunghezza L' = U-1
• Utilizza lo schema di calcolo privato simmetrico Kc volte, ottenendo separatamente ogni combinazione lineare
• Costruisce polinomi di query utilizzando codifica di Lagrange, proteggendo la privacy del compito computazionale

Risultati Sperimentali

Risultati Teorici

Teorema 3 (Ottimalità per Kc=1): Per il problema di aggregazione sicura multi-messaggio (K,U,Kc), quando U≤K-1 e Kc=1, la regione di capacità è: $\mathcal{R}^* = \{(R_1,R_2) : R_1 \geq 1, R_2 \geq \frac{1}{U}\}$

Teorema 5 (Raggiungibilità per 2≤Kc<U): Quando 2≤Kc<U≤K-1, la tupla di velocità $(R_1 = 1, R_2 = \frac{K_c}{U-1})$ è raggiungibile.

Teorema 6 (Limite Inverso): Qualsiasi velocità raggiungibile deve soddisfare: $R_1 \geq 1, R_2 \geq \frac{K_c}{U}$

Analisi delle Prestazioni

1. Ottimalità: Il caso Kc=1 raggiunge l'ottimalità teorica
2. Quasi-Ottimalità: Nel caso 2≤Kc<U, la velocità del primo round è ottimale, la velocità del secondo round è ottimale entro un fattore 2: $\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2$
3. Confronto con il Baseline: Rispetto allo schema di ripetizione diretta, il nuovo schema riduce la velocità del primo round da Kc a 1, e aumenta la velocità del secondo round da Kc/U a Kc/(U-1)

Lavori Correlati

Aggregazione Sicura

• Aggregazione Sicura con Sicurezza Teorica dell'Informazione: Zhao e Sun hanno proposto per la prima volta la formalizzazione teorica dell'informazione, realizzando la regione di capacità {(R1,R2) : R1≥1, R2≥1/U}
• Aggregazione Sicura Pratica: LightSecAgg riduce significativamente il numero di chiavi richieste disaccoppiando il processo di generazione delle chiavi

Recupero Privato di Informazioni e Calcolo

• Recupero Privato di Informazioni (PIR): Consente al server di recuperare privatamente messaggi da un database distribuito
• Calcolo Privato (PC): Estende il framework PIR includendo il calcolo lineare dei messaggi
• Calcolo Privato Simmetrico: Protegge simultaneamente la privacy del compito computazionale del server e la sicurezza dei dati degli utenti

Apprendimento Multi-Compito

• Apprendimento Coordinato: Più compiti collaborano condividendo informazioni e risorse, migliorando l'efficienza complessiva di apprendimento
• Rappresentazione Comune: I compiti beneficiano di rappresentazioni comuni, gradienti o componenti condivisi

Conclusioni e Discussione

Conclusioni Principali

1. Formalizza per la prima volta il problema dell'aggregazione sicura multi-messaggio con privacy della domanda
2. Realizza la regione di velocità di comunicazione ottimale per Kc=1
3. Realizza prestazioni ottimali nel primo round e quasi-ottimali nel secondo round per 2≤Kc<U
4. Fornisce un framework di analisi teorica completo

Limitazioni

1. Regione Aperta: La caratterizzazione della regione di capacità per Kc≥U rimane irrisolta
2. Dimensione della Chiave: Non è stata ottimizzata la minimizzazione della dimensione della chiave richiesta
3. Praticità: La complessità di implementazione degli schemi teorici nei sistemi reali è elevata
4. Scalabilità: La scalabilità ai compiti computazionali non lineari è limitata

Direzioni Future

1. Caratterizzazione Completa della Regione di Capacità: Risolvere il problema di ottimalità per il caso Kc≥U
2. Ottimizzazione della Chiave: Minimizzare la dimensione della chiave richiesta per migliorare la praticità
3. Implementazione di Sistema: Sviluppare prototipi di sistema effettivamente distribuibili
4. Estensione Non Lineare: Estendere ai compiti computazionali non lineari

Valutazione Approfondita

Punti di Forza

1. Contributi Teorici Significativi: Combina innovativamente l'aggregazione sicura e la privacy della domanda, colmando un importante vuoto teorico
2. Forte Innovazione Metodologica: Combina abilmente la crittografia moltiplicativa e il calcolo privato simmetrico, con un approccio tecnico innovativo
3. Analisi Teorica Completa: Fornisce prove rigorose di raggiungibilità e analisi di limiti inversi
4. Significato Pratico Rilevante: Risolve importanti problemi di protezione della privacy nell'apprendimento federato

Insufficienze

1. Ambito di Applicabilità Limitato: Considera solo compiti computazionali lineari, le applicazioni pratiche potrebbero richiedere operazioni non lineari
2. Complessità di Implementazione Elevata: Particolarmente nel caso 2≤Kc<U, l'implementazione del calcolo privato simmetrico è relativamente complessa
3. Vincoli sui Parametri: Il vincolo Kc<U potrebbe essere eccessivamente restrittivo in alcuni scenari applicativi
4. Mancanza di Validazione Sperimentale: Mancano implementazioni di sistemi reali e test di prestazioni

Impatto

1. Valore Accademico: Fornisce un nuovo framework teorico per il calcolo multi-party sicuro e l'apprendimento federato
2. Potenziale Pratico: Fornisce fondamenta teoriche per l'apprendimento distribuito con protezione della privacy
3. Riproducibilità: I risultati teorici sono chiari, ma l'implementazione pratica richiede notevole lavoro di ingegneria

Scenari Applicabili

1. Apprendimento Federato: Aggregazione con protezione della privacy nell'apprendimento federato multi-compito
2. Statistica Distribuita: Sistemi distribuiti che richiedono il calcolo di più quantità statistiche
3. Analisi con Protezione della Privacy: Scenari di analisi dei dati in finanza, sanità e altri settori con rigorosi requisiti di privacy

Bibliografia

L'articolo cita molteplici riferimenti importanti, inclusi:

• Lavori di Zhao & Sun sull'aggregazione sicura con sicurezza teorica dell'informazione
• Risultati di Sun & Jafar sulla capacità del recupero privato di informazioni e del calcolo privato
• Schema di calcolo privato polinomiale simmetrico di Zhu et al.
• Risultati classici di Shannon sulla sicurezza teorica dell'informazione

Valutazione Complessiva: Questo è un articolo teorico di alta qualità che fornisce contributi importanti nell'intersezione tra aggregazione sicura e calcolo con protezione della privacy. Sebbene vi sia ancora spazio per miglioramenti nella praticità, la sua innovazione teorica e l'analisi rigorosa forniscono una base solida per la ricerca successiva.