Technisches Resümee: NFSA: Non-Forward Secure Aggregation mit einem Server via Two-Layer Secret Sharing

1. Problemstellung

Federated Learning (FL) ermöglicht das kollaborative Training von Modellen unter Wahrung der lokalen Daten, doch die Übertragung von Modellaktualisierungen (Gradienten) birgt dennoch Datenschutzrisiken. Protokolle zur sicheren Aggregation sind erforderlich, um sicherzustellen, dass der Server nur das aggregierte Modell und nicht die individuellen Benutzereingaben lernt.

Bestehende serverbasierte Protokolle zur sicheren Aggregation stehen vor zwei primären Herausforderungen, insbesondere in Cross-Device-Szenarien:

1. Benutzer-Dropout und Schlüsselweiterleitung: Um Benutzer-Dropouts zu handhaben, nutzen Protokolle oft Schwellenwert-Secret-Sharing (SS), wie etwa Shamir's SS, bei dem Benutzer Geheimnisse mit „Holdern“ (anderen Benutzern oder Komitees) teilen. In Single-Server-Einstellungen können Benutzer nicht direkt miteinander kommunizieren; daher muss der Server diese Secret-Shares weiterleiten. Diese Weiterleitung führt zu einem erheblichen Kommunikationsaufwand ($O(NM)$ pro Runde, wobei $N$ die Anzahl der Benutzer und $M$ die Anzahl der Holder ist) und Sicherheitsrisiken, da der Server darauf vertrauen muss, die weitergeleiteten Shares nicht zu manipulieren oder zu lernen (was oft eine authentifizierte Verschlüsselung erfordert).
2. Kommunikationseffizienz: Hochdimensionale Modellparameter und eine große Anzahl von Benutzern erzeugen Bandbreitenengpässe. Jüngste „One-Shot“-Aggregationsschemata unter Verwendung von Key-homomorphic Pseudo-Random Functions (KhPRF) reduzieren die Interaktionsrunden, leiden jedoch unter „Ciphertext-Expansion“. Fast KhPRF (basierend auf LWR/LWE) führt ein Rauschen ein, das proportional zur Anzahl der Benutzer ist, was zusätzlichen Platz in den Modellaktualisierungen erforderlich macht, um Interferenzen zu vermeiden, was das gesamte Kommunikationsvolumen erhöht ($O(RN \log N)$).

2. Methodik

Das Paper schlägt NFSA (Non-Forward Secure Aggregation) vor, ein Protokoll, das für ein Single-Server-FL-Szenario entwickelt wurde, die Weiterleitung von Geheimnisdaten durch den Server eliminiert und den Kommunikationsaufwand durch eine neuartige Kodierungsmethode reduziert.

2.1 Two-Layer Secret Sharing (TLSS)

Um das Weiterleitungsproblem zu adressieren, führen die Autoren TLSS ein, welches zwei Schichten des Secret Sharing kombiniert, um eine sichere Aggregation ohne das Relaisen sensibler Shares durch den Server zu ermöglichen:

• Layer 1 (Threshold SS): Verwendet Shamir's Secret Sharing, um Benutzer-Dropouts zu handhaben. Ein Geheimnis eines Benutzers (z. B. ein KhPRF-Schlüssel) wird in Shares $s_m$ aufgeteilt, die an $M$ Holder verteilt werden.
• Layer 2 (Additive SS mit PRF): Anstatt $s_m$ direkt an den Server zur Weiterleitung zu senden, teilt der Benutzer $s_m$ in zwei additive Shares auf: $s_m = s_{m}^{A1} + s_{m}^{A2} \mod p$.
  • $s_{m}^{A1}$ wird unter Verwendung einer Pseudo-Random Function (PRF) generiert, die durch einen vorverhandelten gemeinsamen Schlüssel $\kappa_{d,m}$ zwischen dem Benutzer und dem Holder $P_m$ definiert ist.
  • $s_{m}^{A2}$ wird als $s_m - s_{m}^{A1} \mod p$ berechnet.
  • Der Benutzer sendet nur $s_{m}^{A2}$ an den Server.
  • Der Server sendet ein Tag an den Holder $P_m$, welcher $s_{m}^{A1}$ unter Verwendung seines gemeinsamen Schlüssels berechnet und es an den Server zurücksendet.
  • Der Server rekonstruiert $s_m = s_{m}^{A1} + s_{m}^{A2}$ und fährt mit der Shamir-Rekonstruktion fort.
• Ergebnis: Der Server leitet keine Secret-Shares zwischen Benutzern und Holdern weiter, wodurch der $O(NM)$ Weiterleitungsaufwand entfällt und die Notwendigkeit einer authentifizierten Verschlüsselung auf den Shares eliminiert wird.

2.2 CRT-Kodierung für Almost KhPRF

Um die durch Almost-KhPRF-Rauschen verursachte Kommunikationsexpansion zu adressieren, schlagen die Autoren eine neue Kodierungsmethode basierend auf den Chinesischen Restsätzen (CRT) vor:

• Problem: Bestehende Methoden maskieren Eingaben $x_i$ als $y_i = \Delta x_i - F(k_i, \tau)$. Um korrekt zu dekodieren, muss $\Delta$ größer als die Anzahl der Benutzer $n$ sein, was die Bitlänge jedes Elements um $\log_2(n+1)$ erhöht.
• Lösung: Die Autoren packen $d_c$ Elemente des Eingangsvektors in eine einzige Ganzzahl unter Verwendung von CRT.
  • Die Eingabeelemente werden auf distinkte Primmoduli $p_i$ erweitert.
  • Diese werden zu einem einzigen Element in $\mathbb{Z}_{p_c}$ (wobei $p_c = \prod p_i$) kombiniert.
  • Die maskierte Aggregation wird auf diesen gepackten Elementen durchgeführt.
• Vorteil: Dies reduziert die Anzahl der KhPRF-Aufrufe um den Faktor $d_c$ und reduziert das gesamte Kommunikationsvolumen erheblich, indem die pro-Element-Expansion durch $\Delta$ vermieden wird.

2.3 Das NFSA-Protokoll

Das Protokoll operiert in zwei Phasen:

1. Offline-Phase: Benutzer und Dekryptoren (Holder) führen eine Schlüsselvereinbarung (Key Agreement, KA) durch, um gemeinsame Schlüssel zu etablieren. Dies ist zustandslos und wird einmalig durchgeführt.
2. Online-Phase (One-Shot):
   • Maskierung: Jeder Benutzer generet einen KhPRF-Schlüssel, teilt ihn via TLSS (indem er nur additive Shares an den Server sendet) und maskiert seine Modellaktualisierung unter Verwendung der CRT-gepackten Almost-KhPRF.
   • Entmaskierung: Dekryptoren berechnen die Summe ihrer additiven Shares (unter Ausnutzung der Homomorphie von TLSS) und senden diese an den Server. Der Server rekonstruiert den globalen KhPRF-Schlüssel, generiert die globale Maske und entmaskiert den aggregierten Ciphertext, um die Modellaktualisierung wiederherzustellen.

3. Wesentliche Beiträge

1. TLSS-Schema: Ein neuartiges Two-Layer-Secret-Sharing-Schema, das die Notwendigkeit der Weiterleitung von Secret-Shares durch einen Server in Single-Server-FL eliminiert. Es reduziert den Kommunikationsaufwand für die Schlüsselteilung und entfernt die Anforderung an eine authentifizierte Verschlüsselung für weitergeleitete Daten.
2. CRT-Kodierung für Almost KhPRF: Eine neue Eingangskodierungsmethode, die mehrere Eingaben mittels des Chinesischen Restsatzes bündelt. Dies reduziert die Anzahl der KhPRF-Aufrufe und mildert das Problem der Modellaktualisierungs-Expansion durch Almost-KhPRF-Rauschen ab, wodurch sowohl der Rechen- als auch der Kommunikationsaufwand gesenkt wird.
3. NFSA-Protokoll: Ein kompaktes One-Shot-Protokoll zur sicheren Aggregation, das TLSS und CRT-Kodierung kombiniert. Es unterstützt die Aggregation hochdimensionaler Daten mit einem einzelnen Server und ohne intermediäre Datenweiterleitung.

4. Experimentelle Ergebnisse

Die Autoren implementierten das Protokoll in Python und verglichen es mit dem State-of-the-Art OPA-Schema (welches Shamir's SS und KhPRF ohne TLSS oder CRT-Packing verwendet).

• TLSS-Performance: Im Vergleich zu traditionellem Shamir's SS mit Weiterleitung reduzierte TLSS den Kommunikationsaufwand der Holder um etwa 57 % und die Rechenzeit um 95 % (bei einem 64-Bit-Modulus) beim Teilen von Geheimnissen mit 50 Holdern. Der Gesamtaufwand war signifikant niedriger, da die Server-Weiterleitung entfiel.
• CRT-Kodierungs-Performance: Die Verwendung von CRT-Packing ($d_c=4$) reduzierte die Maskierungszeit der Benutzer um den Faktor 3,72$\times$ und den Kommunikationsverkehr um den Faktor 1,40$\times$ im Vergleich zu OPA.
• End-to-End NFSA-Performance:
  • Benutzer-Overhead: Für 100 Benutzer verbesserte NFSA die Kommunikationseffizienz um fast das 100-fache (speziell für die Kommunikation der Dekryptoren) und reduzierte die Rechenzeit der Benutzer um 51 % bis 75 % (abhängig von der Eingabelänge).
  • Server-Overhead: Die Rechenzeit des Servers wurde um etwa 50 % reduziert, und der Kommunikationsverkehr des Servers sank um 25 % im Vergleich zu OPA.
  • Dekryptor-Overhead: Der Kommunikationsaufwand der Dekryptoren wurde von ~19 MB (OPA) auf ~0,19 MB (NFSA) reduziert, was einer Reduktion um fast das 100-fache entspricht.

5. Bedeutung und Ansprüche

Das Paper behauptet, dass NFSA den kritischen Engpass der Server-Weiterleitung bei der sicheren Aggregation adressiert. Durch die Entkopplung des Secret-Sharing-Prozesses von der Relay-Rolle des Servers wird die Angriffsfläche verringert und die Kommunikationskosten gesenkt. Die Integration der CRT-Kodierung optimiert zudem die Effizienz von Almost-KhPRF weiter und macht es für hochdimensionale FL-Modelle praktikabel.

Die Autoren positionieren NFSA als eine hocheffiziente Lösung für Semi-Honest-Umgebungen. Sie räumen ein, dass OPA in Malicious-Settings stärkere Garantien bietet (durch Verifizierungsmechanismen wie SCRAPE und ZKP), NFSA jedoch eine überlegene Effizienz im Semi-Honest-Modell erreicht. Die Arbeit legt nahe, dass NFSA skalierbar und praktikabel für reale FL-Anwendungen ist, wenngleich zukünftige Arbeit notwendig ist, um die Verifizierbarkeit auf Malicious-Settings auszuweiten und die Verifizierung von CRT-gepackten Eingaben zu verfeinern.