Technische Samenvatting: NFSA: Non-Forward Secure Aggregation met één server via Two-Layer Secret Sharing

1. Probleemstelling

Federated Learning (FL) maakt collaboratieve modeltraining mogelijk terwijl data lokaal blijft, maar de transmissie van modelupdates (gradiënten) vormt nog steeds privacyrisico's. Protocollen voor beveiligde aggregatie zijn vereist om ervoor te zorgen dat de server alleen het geaggregeerde model leert, en niet de individuele gebruikersinputs.

Bestaande servergebaseerde protocollen voor beveiligde aggregatie staan voor twee primaire uitdagingen, met name in cross-device scenario's:

1. User Dropout en Key Forwarding: Om gebruikersuitval (dropouts) op te vangen, maken protocollen vaak gebruik van threshold Secret Sharing (SS), zoals Shamir's SS, waarbij gebruikers geheime sleutels delen met "holders" (andere gebruikers of commissies). In single-server settings kunnen gebruikers niet direct met elkaar communiceren; daarom moet de server deze geheime shares doorsturen (forwarding). Deze forwarding introduceert een aanzienlijke communicatie-overhead ($O(NM)$ per ronde, waarbij $N$ het aantal gebruikers is en $M$ het aantal holders) en beveiligingsrisico's, aangezien de server erop moet vertrouwen dat hij de doorgestuurde shares niet aanpast of leert kennen (vaak is hiervoor Authenticated Encryption nodig).
2. Communicatie-efficiëntie: Hoogdimensionele modelparameters en een groot aantal gebruikers creëren bandbreedte-bottlenecks. Recente "one-shot" aggregatieschema's die gebruikmaken van Key-homomorphic Pseudo-Random Functions (KhPRF) verminderen het aantal interactierondes, maar lijden aan "ciphertext expansie". Almost KhPRF (gebaseerd op LWR/LWE) introduceert ruis die proportioneel is aan het aantal gebruikers, wat extra ruimte in modelupdates vereist om interferentie te voorkomen, wat het totale communicatievolume verhoogt ($O(RN \log N)$).

2. Methodologie

Het artikel stelt NFSA (Non-Forward Secure Aggregation) voor, een protocol ontworpen voor een single-server FL-scenario dat de noodzaak elimineert voor de server om geheime data door te sturen en de communicatie-overhead vermindert via een nieuwe encodemethode.

2.1 Two-Layer Secret Sharing (TLSS)

Om het forwarding-probleem aan te pakken, introduceren de auteurs TLSS, dat twee lagen van secret sharing combineert om beveiligde aggregatie mogelijk te maken zonder dat de server gevoelige shares hoeft door te sturen:

• Laag 1 (Threshold SS): Gebruikt Shamir's Secret Sharing om gebruikersuitval af te handelen. Een geheime waarde van een gebruiker (bijv. een KhPRF-sleutel) wordt gesplitst in shares $s_m$ die worden verdeeld over $M$ holders.
• Laag 2 (Additive SS met PRF): In plaats van $s_m$ direct naar de server te sturen voor forwarding, splitst de gebruiker $s_m$ in twee additive shares: $s_m = s_{m}^{A1} + s_{m}^{A2} \mod p$.
  • $s_{m}^{A1}$ wordt gegenereerd met behulp van een Pseudo-Random Function (PRF) die wordt aangestuurd door een vooraf onderhandelde gedeelde sleutel $\kappa_{d,m}$ tussen de gebruiker en holder $P_m$.
  • $s_{m}^{A2}$ wordt berekend als $s_m - s_{m}^{A1} \mod p$.
  • De gebruiker stuurt alleen $s_{m}^{A2}$ naar de server.
  • De server stuurt een tag naar de holder $P_m$, die $s_{m}^{A1}$ berekent met behulp van hun gedeelde sleutel en deze terugstuurt naar de server.
  • De server reconstrueert $s_m = s_{m}^{A1} + s_{m}^{A2}$ en gaat verder met de Shamir-reconstructie.
• Resultaat: De server stuurt nooit geheime shares tussen gebruikers en holders door, waardoor de $O(NM)$ forwarding-overhead en de noodzaak voor Authenticated Encryption op shares worden geëlimineerd.

2.2 CRT Encoding voor Almost KhPRF

Om de communicatie-expansie veroorzaakt door almost KhPRF-ruis aan te pakken, stellen de auteurs een nieuwe encodemethode voor op basis van de Chinese Reststelling (CRT):

• Probleem: Bestaande methoden maskeren inputs $x_i$ als $y_i = \Delta x_i - F(k_i, \tau)$. Om correct te decoderen, moet $\Delta$ groter zijn dan het aantal gebruikers $n$, wat de bitlengte van elk element met $\log_2(n+1)$ verhoogt.
• Oplossing: De auteurs verpakken $d_c$ elementen van de inputvector in een enkel getal met behulp van CRT.
  • Inputelementen worden uitgebreid naar verschillende priemmoduli $p_i$.
  • Deze worden gecombineerd in een enkel element in $\mathbb{Z}_{p_c}$ (waarbij $p_c = \prod p_i$).
  • De gemaskeerde aggregatie wordt uitgevoerd op deze verpakte elementen.
• Voordeel: Dit vermindert het aantal KhPRF-aanroepen met een factor $d_c$ en vermindert het totale communicatievolume aanzienlijk door de per-element expansie van $\Delta$ te vermijden.

2.3 Het NFSA-protocol

Het protocol werkt in twee fasen:

1. Offline Fase: Gebruikers en decryptors (holders) voeren een Key Agreement (KA) uit om gedeelde sleutels vast te stellen. Dit is stateless en wordt eenmalig uitgevoerd.
2. Online Fase (One-Shot):
   • Masking: Elke gebruiker genereert een KhPRF-sleutel, deelt deze via TLSS (door alleen additive shares naar de server te sturen) en maskeert hun modelupdate met de CRT-verpakte almost KhPRF.
   • Unmasking: Decryptors berekenen de som van hun additive shares (gebruikmakend van de TLSS-homomorfie) en sturen deze naar de server. De server reconstrueert de globale KhPRF-sleutel, genereert de globale maskering en ontmaskert het geaggregeerde ciphertext om de modelupdate te herstellen.

3. Belangrijkste Bijdragen

1. TLSS-schema: Een nieuw twee-laags secret sharing schema dat de noodzaak voor de server om geheime shares door te sturen in single-server FL elimineert. Het vermindert de communicatie-overhead voor het delen van sleutels en heft de vereiste voor authenticated encryption op doorgegeven data op.
2. CRT Encoding voor Almost KhPRF: Een nieuwe input-encodemethode die de Chinese Reststelling gebruikt om meerdere inputs te batchen. Dit vermindert het aantal KhPRF-aanroepen en mitigeert het probleem van de modelupdate-expansie veroorzaakt door almost KhPRF-ruis, wat zowel de computationele als de communicatie-overhead verlaagt.
3. NFSA-protocol: Een compact, one-shot secure aggregation protocol dat TLSS en CRT-encoding combineert. Het ondersteunt aggregatie van hoogdimensionele data met een enkele server en zonder tussenkomst van data-forwarding.

4. Experimentele Resultaten

De auteurs hebben het protocol geïmplementeerd in Python en vergeleken het met het state-of-the-art OPA-schema (dat Shamir's SS en KhPRF gebruikt zonder TLSS of CRT-packing).

• TLSS Prestaties: Vergeleken met traditionele Shamir's SS met forwarding, verminderde TLSS de communicatie-overhead voor holders met ongeveer 57% en de rekentijd met 95% (voor een 64-bit modulus) bij het delen van geheimen met 50 holders. De totale overhead was aanzienlijk lager door het elimineren van server-forwarding.
• CRT Encoding Prestaties: Het gebruik van CRT-packing ($d_c=4$) verminderde de masking-tijd van de gebruiker met 3.72$\times$ en het communicatieverkeer met 1.40$\times$ vergeleken met OPA.
• End-to-End NFSA Prestaties:
  • Gebruikers-overhead: Voor 100 gebruikers verbeterde NFSA de communicatie-efficiëntie met bijna 100 keer (specifiek voor decryptor-communicatie) en verminderde het de rekentijd van de gebruiker met 51% tot 75% (afhankelijk van de inputlengte).
  • Server-overhead: De rekentijd van de server werd met ongeveer 50% verminderd, en het communicatieverkeer van de server werd met 25% verminderd vergeleken met OPA.
  • Decryptor-overhead: De communicatie van de decryptor werd verminderd van ~19MB (OPA) naar ~0.19MB (NFSA), een reductie van bijna 100 keer.

5. Betekenis en Claims

Het artikel claimt dat NFSA het cruciale knelpunt van server-forwarding in beveiligde aggregatie aanpakt. Door het geheime sharing-proces los te koppelen van de relay-rol van de server, wordt het aanvalsoppervlak en de communicatiekosten aanzienlijk verlaagd. De integratie van CRT-encoding optimaliseert verder de efficiëntie van almost KhPRF, waardoor het bruikbaar wordt voor hoogdimensionele FL-modellen.

De auteurs positioneren NFSA als een zeer efficiënte oplossing voor semi-honest omgevingen. Ze erkennen dat hoewel OPA sterkere garanties biedt in malicious settings (via verificatiemechanismen zoals SCRAPE en ZKP), NFSA een superieure efficiëntie bereikt in het semi-honest model. Het werk suggereert dat NFSA schaalbaar en praktisch is voor real-world FL-toepassingen, hoewel toekomstig werk nodig is om de verifieerbaarheid naar malicious settings uit te breiden en de verificatie van CRT-gepakte inputs te verfijnen.