Riepilogo Tecnico: NFSA: Aggregazione Non-Forward Secure con un Singolo Server tramite Secret Sharing a Due Livelli

1. Definizione del Problema

L'Apprendimento Federato (Federated Learning, FL) consente l'addestramento collaborativo di modelli mantenendo i dati locali, ma la trasmissione degli aggiornamenti del modello (gradienti) pone comunque dei rischi per la privacy. Sono necessari protocolli di aggregazione sicura per garantire che il server apprenda solo il modello aggregato e non i singoli input degli utenti.

I protocolli di aggregazione sicura basati su server affrontano due sfide primarie, in particolare negli scenari cross-device:

1. Dropout degli Utenti e Forwarding delle Chiavi: Per gestire gli dropout degli utenti, i protocolli utilizzano spesso lo Secret Sharing (SS) a soglia, come lo Shamir's SS, dove gli utenti condividono le chiavi segrete con dei "holder" (altri utenti o comitati). Nei contesti con singolo server, gli utenti non possono comunicare direttamente; pertanto, il server deve inoltrare queste quote segrete (secret shares). Questo inoltro introduce un overhead di comunicazione significativo ($O(NM)$ per round, dove $N$ è il numero di utenti e $M$ il numero di holder) e rischi di sicurezza, poiché il server deve essere affidabile nel non manomettere o apprendere le quote inoltrate (spesso richiedendo la Crittografia Autenticata).
2. Efficienza della Comunicazione: I parametri del modello ad alta dimensionalità e l'elevato numero di utenti creano colli di bottiglia nella larghezza di banda. Gli approcci recenti "one-shot" di aggregazione utilizzando funzioni pseudo-casuali chiave-omomorfiche (KhPRF) riducono i round di interazione ma soffrono di "espansione del ciphertext". L'Almost KhPRF (basata su LWR/LWE) introduce un rumore proporzionale al numero di utenti, rendendo necessario spazio extra negli aggiornamenti del modello per evitare interferenze, il che aumenta il volume totale di comunicazione ($O(RN \log N)$).

2. Metodologia

Il documento propone NFSA (Non-Forward Secure Aggregation), un protocollo progettato per uno scenario di FL con singolo server che elimina la necessità per il server di inoltrare dati segreti e riduce l'overhead di comunicazione attraverso un nuovo metodo di codifica.

2.1 Two-Layer Secret Sharing (TLSS)

Per affrontare il problema dell'inoltro, gli autori introducono il TLSS, che combina due livelli di secret sharing per consentire l'aggregazione sicura senza che il server debba trasmettere quote sensibili:

• Livello 1 (Threshold SS): Utilizza lo Shamir's Secret Sharing per gestire i dropout degli utenti. Il segreto di un utente (ad esempio, una chiave KhPRF) viene diviso in quote $s_m$ distribuite a $M$ holder.
• Livello 2 (Additive SS con PRF): Invece di inviare $s_m$ direttamente al server per l'inoltro, l'utente divide $s_m$ in due quote additive: $s_m = s_{m}^{A1} + s_{m}^{A2} \mod p$.
  • $s_{m}^{A1}$ viene generato utilizzando una Funzione Pseudo-Casuale (PRF) basata su una chiave condivisa pre-negoziata $\kappa_{d,m}$ tra l'utente e l'holder $P_m$.
  • $s_{m}^{A2}$ viene calcolato come $s_m - s_{m}^{A1} \mod p$.
  • L'utente invia solo $s_{m}^{A2}$ al server.
  • Il server invia un tag all'holder $P_m$, il quale calcola $s_{m}^{A1}$ usando la propria chiave condivisa e lo rimanda al server.
  • Il server ricostruisce $s_m = s_{m}^{A1} + s_{m}^{A2}$ e procede con la ricostruzione di Shamir.
• Risultato: Il server non inoltra mai le quote segrete tra utenti e holder, eliminando l'overhead di forwarding $O(NM)$ e la necessità di Crittografia Autenticata sulle quote.

2.2 Codifica CRT per Almost KhPRF

Per affrontare l'espansione della comunicazione causata dal rumore dell'Almost KhPRF, gli autori propongono un nuovo metodo di codifica basato sul Teorema Cinese del Resto (CRT):

• Problema: I metodi esistenti mascherano gli input $x_i$ come $y_i = \Delta x_i - F(k_i, \tau)$. Per decodificare correttamente, $\Delta$ deve essere maggiore del numero di utenti $n$, aumentando la lunghezza in bit di ogni elemento di $\log_2(n+1)$.
• Soluzione: Gli autori impacchettano $d_c$ elementi del vettore di input in un singolo intero utilizzando il CRT.
  • Gli elementi di input vengono estesi a distinti moduli primi $p_i$.
  • Questi vengono combinati in un singolo elemento in $\mathbb{Z}_{p_c}$ (dove $p_c = \prod p_i$).
  • L'aggregazione mascherata viene eseguita su questi elementi impacchettati.
• Beneficio: Questo riduce il numero di chiamate KhPRF di un fattore $d_c$ e riduce significativamente il volume totale di comunicazione evitando l'espansione per elemento del $\Delta$.

2.3 Il Protocollo NFSA

Il protocollo opera in due fasi:

1. Fase Offline: Gli utenti e i decisori (holder) eseguono un Accordo sulle Chiavi (KA) per stabilire chiavi condivise. Questa fase è stateless e viene eseguita una sola volta.
2. Fase Online (One-Shot):
   • Mascheramento: Ogni utente genera una chiave KhPRF, la condivide tramite TLSS (inviando solo le quote additive al server) e maschera il proprio aggiornamento del modello utilizzando l'Almost KhPRF impacchettata tramite CRT.
   • Smascheramento: I decisori calcolano la somma delle loro quote additive (sfruttando l'omomorfismo del TLSS) e le inviano al server. Il server ricostruisce la chiave globale KhPRF, genera la maschera globale e smaschera il ciphertext aggregato per recuperare l'aggiornamento del modello.

3. Contributi Chiave

1. Schema TLSS: Un nuovo schema di secret sharing a due livelli che elimina la necessità per il server di inoltrare le quote segrete in scenari di FL con singolo server. Riduce l'overhead di comunicazione per la condivisione delle chiavi e rimuove il requisito di crittografia autenticata sui dati inoltrati.
2. Codifica CRT per Almost KhPRF: Un nuovo metodo di codifica dell'input che utilizza il Teorema Cinese del Resto per il batching di molteplici input. Questo riduce le chiamate KhPRF e mitiga il problema dell'espansione dell'aggiornamento del modello causato dal rumore dell'Almost KhPRF, abbassando sia l'overhead computazionale che quello di comunicazione.
3. Protocollo NFSA: Un protocollo di aggregazione sicura compatto e "one-shot" che combina TLSS e codifica CRT. Supporta l'aggregazione di dati ad alta dimensionalità con un singolo server e senza inoltro intermedio di dati.

4. Risultati Sperimentali

Gli autori hanno implementato il protocollo in Python e lo hanno confrontato con lo schema OPA all'avanguardia (che utilizza lo Shamir's SS e l'Almost KhPRF senza TLSS o packing CRT).

• Performance TLSS: Rispetto allo Shamir's SS tradizionale con forwarding, il TLSS ha ridotto l'overhead di comunicazione degli holder di circa il 57% e il tempo di calcolo del 95% (per modulo a 64 bit) durante la condivisione dei segreti con 50 holder. L'overhead totale era significativamente inferiore grazie all'eliminazione del forwarding del server.
• Performance Codifica CRT: L'uso del packing CRT ($d_c=4$) ha ridotto il tempo di mascheramento dell'utente di 3,72× e il traffico di comunicazione di 1,40× rispetto a OPA.
• Performance End-to-End NFSA:
  • Overhead Utente: Per 100 utenti, NFSA ha migliorato l'efficienza della comunicazione di quasi 100 volte (specificamente per la comunicazione dei decisori) e ha ridotto il tempo di calcolo dell'utente del 51% - 75% (a seconda della lunghezza dell'input).
  • Overhead Server: Il tempo di calcolo del server è stato ridotto di circa il 50%, e il traffico di comunicazione del server è stato ridotto del 25% rispetto a OPA.
  • Overhead Decisore: La comunicazione dei decisori è stata ridotta da ~19MB (OPA) a ~0,19MB (NFSA), una riduzione di quasi 100 volte.

5. Significato e Assertions

Il documento afferma che NFSA affronta il collo di bottiglia critico del forwarding del server nell'aggregazione sicura. Decoppiando il processo di secret sharing dal ruolo di relay del server, esso riduce significativamente la superficie di attacco e i costi di comunicazione. L'integrazione della codifica CRT ottimizza ulteriormente l'efficienza dell'Almost KhPRF, rendendola praticabile per modelli FL ad alta dimensionalità.

Gli autori posizionano NFSA come una soluzione altamente efficiente per ambienti semi-onesti (semi-honest). Riconoscono che, sebbene OPA offra garanzie più forti in contesti malevoli (tramite meccanismi di verifica come SCRAPE e ZKP), NFSA raggiunge un'efficienza superiore nel modello semi-onesto. Il lavoro suggerisce che NFSA sia scalabile e pratico per applicazioni FL reali, sebbene siano necessari futuri sviluppi per estendere la sua verificabilità ai contesti malevoli e perfezionare la verifica degli input impacchettati tramite CRT.