Multi-Message Secure Aggregation with Demand Privacy

Grundlegende Informationen

• Paper-ID: 2504.20639
• Titel: Multi-Message Secure Aggregation with Demand Privacy
• Autoren: Chenyi Sun, Ziting Zhang, Kai Wan (Huazhong University of Science and Technology), Giuseppe Caire (Technische Universität Berlin)
• Klassifizierung: cs.IT math.IT
• Veröffentlichungsdatum: 13. Oktober 2025 (arXiv v2)
• Paper-Link: https://arxiv.org/abs/2504.20639

Zusammenfassung

Dieses Paper untersucht ein Multi-Message-Secure-Aggregation-Problem mit Anfrageprivatsphäre, bei dem ein Server darauf abzielt, Kc≥1 Linearkombinationen lokaler Eingaben von K verteilten Benutzern zu berechnen. Das Problem adressiert zwei Aufgaben: (1) Sicherheit, um sicherzustellen, dass der Server nur die erforderlichen Linearkombinationen erhält, ohne andere Informationen über Benutzereingaben preiszugeben; (2) Privatsphäre, um zu verhindern, dass Benutzer die Rechenaufgaben des Servers erfahren. Darüber hinaus wird die Auswirkung von Benutzerausfällen berücksichtigt, wobei bis zu K-U Benutzer ausfallen können und ihre Identitäten nicht vorab vorhersehbar sind. Die Autoren schlagen zwei separate Schemata für die Fälle Kc=1 und 2≤Kc<U vor. Für Kc=1 wird eine Methode eingeführt, die Serveranfragen durch multiplikative Verschlüsselung mit Zufallsvariablen schützt; für 2≤Kc<U wird robuste symmetrische private Berechnung verwendet, um Linearkombinationen von Schlüsseln in der zweiten Runde wiederherzustellen.

Forschungshintergrund und Motivation

Problemdefinition

Föderiertes Lernen ermöglicht verteilten Benutzern, unter Koordination eines zentralen Servers ein globales Modell gemeinsam zu trainieren. Allerdings können Modellaktualisierungen immer noch Informationen über lokale Benutzerdaten preisgeben. Um die Sicherheit weiter zu erhöhen, wurde Secure Aggregation eingeführt, um sicherzustellen, dass der Server nur aggregierte Aktualisierungen erhält, ohne zusätzliche Informationen über Benutzerdaten zu erhalten.

Forschungsmotivation

1. Multi-Task-Learning-Anforderungen: Im Vergleich zu Single-Task-Learning kann Multi-Task-Learning mehrere Ergebnisse nutzen, um die Gesamtleistung des Modelltrainings zu verbessern, durch Informations- und Ressourcenteilung die Lerneffizienz zu erhöhen.
2. Einschränkungen bestehender Methoden:
   • Bestehende informationstheoretische Secure-Aggregation-Probleme konzentrieren sich hauptsächlich auf den Fall Kc=1
   • Mangel an Datenschutz für Serverrechenaufgaben
   • Notwendigkeit, Sicherheit und Privatsphäre bei Benutzerausfällen zu gewährleisten
3. Praktische Anforderungen: In realen Föderiertes-Learning-Szenarien muss der Server möglicherweise mehrere verschiedene Linearkombinationen berechnen, während Benutzer die spezifischen Rechenaufgaben des Servers nicht kennen sollten.

Kernbeiträge

1. Neue Problemformalisierung: Erstmals wird das Multi-Message-Secure-Aggregation-Problem mit Anfrageprivatsphäre vorgeschlagen, was den Forschungsumfang traditioneller Secure Aggregation erweitert.
2. Optimales Schema (Kc=1): Ein Secure-Aggregation-Schema wird vorgeschlagen, das multiplikative Verschlüsselung von Anfragen mit additiver Modellverschlüsselung kombiniert und die optimale Kommunikationsratenregion erreicht, die der Kapazität des Secure-Aggregation-Problems ohne Privatspährebeschränkungen entspricht.
3. Näherungsweise optimales Schema (2≤Kc<U): Durch Nutzung symmetrischer privater Berechnungsschemata wird die Baseline-Methode, die das erste Schema Kc-mal wiederholt, erheblich verbessert. Die erste Runde ist optimal, die zweite Runde ist innerhalb eines Faktors von 2 optimal.
4. Theoretische Analyse: Vollständige Erreichbarkeitsnachweise und Umkehrschrankenanalyse werden bereitgestellt, um die theoretische Grundlage des Problems zu etablieren.

Methodische Details

Systemmodell

Teilnehmer:

• 1 Server und K nicht-kolludierende Benutzer (K≥2)
• Benutzer i hält Eingabevektor Wi und Schlüssel Pi
• Wi enthält L unabhängig und identisch verteilte gleichmäßige Symbole, definiert über endlichem Körper Fq

Zielfunktion: Der Server berechnet die lineare Abbildung: $g(W_1, \cdots, W_K) = F[W_1, \cdots, W_K]^T$

wobei F eine Kc×K-dimensionale Koeffizientenmatrix ist: $F = \begin{pmatrix} a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}$

Kommunikationsmodell:

• Erste Runde: Server sendet Anfrage Q1,i an Benutzer i, Benutzer i antwortet mit Nachricht Xi
• Zweite Runde: Server informiert die Menge der aktiven Benutzer U1, sendet Anfrage Q^{U1}_{2,i}, Benutzer i sendet Y^{U1}_i

Einschränkungen

1. Dekodierbarkeit: Der Server kann die erforderlichen Linearkombinationen fehlerfrei berechnen
2. Sicherheit: Der Server kann keine Benutzereingabeinformationen über die Zielberechnungsergebnisse hinaus erhalten
3. Privatsphäre: Benutzer können die Anfragematrix F des Servers nicht ableiten

Schema für den Fall Kc=1

Kernidee

Kombination von multiplikativer Anfrageverschlüsselung und additiver Modellverschlüsselung, wobei Serveranfragen durch Zufallsvariable t verschlüsselt werden.

Detaillierte Schritte

Phase 1 (Anfragegenerierung):

• Server wählt zufällig t ∈ Fq{0}
• Definiert Anfrage: $Q_{1,i} = \frac{1}{ta_{1,i}}$, i ∈ K

Phase 2 (Schlüsselgenerierung):

• Für jeden Benutzer i wird Zi generiert, gleichmäßig verteilt auf F^L_q
• Zi wird in U Unterschlüssel aufgeteilt: Zim ∈ F^{L/U}_q
• MDS-Matrix M wird zur Kodierung verwendet: $[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}$

Phase 3 (Erste Rundenübertragung):

• Benutzer i sendet: $X_i = W_i + Q_{1,i}Z_i$

Phase 4 (Zweite Rundenübertragung):

• Benutzer j ∈ U1 sendet aggregierte kodierte Unterschlüssel: $\sum_{i \in U_1}[\tilde{Z}_i]_j$
• Server stellt $\sum_{i \in U_1} Z_i$ durch MDS-Dekodierung wieder her

Dekryptionsprozess

Der Server berechnet: $\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$

Da $t \sum_{i \in U_1} a_{1,i}W_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i$, kann der Server die Ziellinearkombination dekodieren.

Schema für den Fall 2≤Kc<U

Kernidee

Nutzung robuster symmetrischer privater Berechnung in der zweiten Rundenübertragung zur Gewährleistung von Sicherheit und Privatsphäre.

Detaillierte Schritte

Phase 1 (Schlüsselgenerierung):

• Für jedes i ∈ K wird Zi zufällig aus F^L_q ausgewählt
• Alle Benutzer teilen Schlüssel: Pi = (Zi)i∈K
• L/(U-1) gemeinsame Zufallsvariablen werden als Schlüsselmaskierung geteilt

Phase 2 (Erste Rundenübertragung):

• Benutzer i sendet: $X_i = W_i + Z_i$

Phase 3 (Zweite Rundenübertragung):

• Server muss Kc Schlüsselkombinationen wiederherstellen: $\sum_{i \in U_1} a_{n,i}Z_i$, n ∈ Kc
• Jeden Schlüssel Zi in Unterschlüssel der Länge L' = U-1 aufteilen
• Symmetrisches privates Berechnungsschema Kc-mal verwenden, um jede Linearkombination separat zu erhalten
• Lagrange-Kodierung zur Konstruktion von Anfragpolynomen verwenden, um Rechenaufgabenprivatsphäre zu schützen

Experimentelle Ergebnisse

Theoretische Ergebnisse

Theorem 3 (Optimalität für Kc=1): Für das (K,U,Kc) Multi-Message-Secure-Aggregation-Problem ist die Kapazitätsregion bei U≤K-1 und Kc=1: $\mathcal{R}^* = \{(R_1,R_2) : R_1 \geq 1, R_2 \geq \frac{1}{U}\}$

Theorem 5 (Erreichbarkeit für 2≤Kc<U): Wenn 2≤Kc<U≤K-1, ist das Ratentupel $(R_1 = 1, R_2 = \frac{K_c}{U-1})$ erreichbar.

Theorem 6 (Umkehrschranke): Jede erreichbare Rate muss erfüllen: $R_1 \geq 1, R_2 \geq \frac{K_c}{U}$

Leistungsanalyse

1. Optimalität: Der Fall Kc=1 erreicht theoretisches Optimum
2. Näherungsweise Optimalität: Im Fall 2≤Kc<U ist die erste Rundenrate optimal, die zweite Rundenrate ist innerhalb eines Faktors von 2 optimal: $\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2$
3. Vergleich mit Baseline: Im Vergleich zur direkten Wiederholungsmethode reduziert das neue Schema die erste Rundenrate von Kc auf 1 und erhöht die zweite Rundenrate von Kc/U auf Kc/(U-1)

Verwandte Arbeiten

Secure Aggregation

• Informationstheoretische Secure Aggregation: Zhao und Sun führten erstmals eine informationstheoretische Formalisierung ein und erreichten die Kapazitätsregion {(R1,R2) : R1≥1, R2≥1/U}
• Praktische Secure Aggregation: LightSecAgg reduziert die erforderliche Schlüsselanzahl erheblich durch Entkopplung des Schlüsselgenerierungsprozesses

Private Information Retrieval und Private Computation

• Private Information Retrieval (PIR): Ermöglicht dem Server, privat Nachrichten aus verteilten Datenbanken abzurufen
• Private Computation (PC): Erweitert das PIR-Framework um lineare Berechnungen von Nachrichten
• Symmetrische Private Computation: Schützt gleichzeitig die Privatsphäre von Serverrechenaufgaben und Benutzerdatensicherheit

Multi-Task-Learning

• Koordiniertes Lernen: Mehrere Aufgaben arbeiten durch Informations- und Ressourcenteilung zusammen, um die Gesamtlerneffizienz zu verbessern
• Gemeinsame Repräsentation: Aufgaben profitieren von gemeinsamen Repräsentationen, Gradienten oder gemeinsamen Komponenten

Schlussfolgerung und Diskussion

Hauptschlussfolgerungen

1. Erstmalige Formalisierung des Multi-Message-Secure-Aggregation-Problems mit Anfrageprivatsphäre
2. Erreichung der optimalen Kommunikationsratenregion für Kc=1
3. Erreichung von erster Runde optimal und zweiter Runde näherungsweise optimal für 2≤Kc<U
4. Bereitstellung eines vollständigen theoretischen Analyserahmens

Einschränkungen

1. Offene Region: Die Kapazitätsregioncharakterisierung für Kc≥U bleibt ungelöst
2. Schlüsselgröße: Minimierung der erforderlichen Schlüsselgröße ist nicht optimiert
3. Praktikabilität: Die theoretische Implementierungskomplexität in realen Systemen ist hoch
4. Skalierbarkeit: Begrenzte Erweiterbarkeit auf nichtlineare Rechenaufgaben

Zukünftige Richtungen

1. Vollständige Kapazitätsregioncharakterisierung: Lösung des Optimalitätsproblems für Kc≥U
2. Schlüsseloptimierung: Minimierung der erforderlichen Schlüsselgröße zur Verbesserung der Praktikabilität
3. Systemimplementierung: Entwicklung praktisch einsetzbarer Systemprototypen
4. Nichtlineare Erweiterung: Erweiterung auf nichtlineare Rechenaufgaben

Tiefgreifende Bewertung

Stärken

1. Signifikante theoretische Beiträge: Bahnbrechende Kombination von Secure Aggregation und Anfrageprivatsphäre, füllt wichtige theoretische Lücke
2. Starke Methodische Innovation: Geschickte Kombination von multiplikativer Verschlüsselung und symmetrischer privater Berechnung, neuartige technische Route
3. Vollständige theoretische Analyse: Strenge Erreichbarkeitsnachweise und Umkehrschrankenanalyse
4. Bedeutende praktische Relevanz: Löst wichtiges Datenschutzproblem im föderiertem Lernen

Schwächen

1. Begrenzte Anwendbarkeit: Berücksichtigt nur lineare Rechenaufgaben, praktische Anwendungen könnten nichtlineare Operationen erfordern
2. Hohe Implementierungskomplexität: Besonders im Fall 2≤Kc<U ist die Implementierung symmetrischer privater Berechnung komplex
3. Parameterbeschränkungen: Die Anforderung Kc<U könnte in einigen Anwendungsszenarien zu restriktiv sein
4. Fehlende experimentelle Validierung: Mangel an praktischer Systemimplementierung und Leistungstests

Einfluss

1. Akademischer Wert: Bietet neuen theoretischen Rahmen für sichere Multi-Party-Berechnung und föderiertes Lernen
2. Praktisches Potenzial: Bietet theoretische Grundlage für datenschutzgerechtes verteiltes maschinelles Lernen
3. Reproduzierbarkeit: Theoretische Ergebnisse sind klar, praktische Implementierung erfordert jedoch erhebliche Ingenieurarbeit

Anwendungsszenarien

1. Föderiertes Lernen: Datenschutzgerechte Aggregation in Multi-Task-Föderiertem Lernen
2. Verteilte Statistik: Verteilte Systeme, die mehrere statistische Größen berechnen müssen
3. Datenschutzgerechte Analyse: Datenanalyseszenarien in Finanzen, Gesundheitswesen und anderen datenschutzkritischen Bereichen

Referenzen

Das Paper zitiert mehrere wichtige Referenzen, einschließlich:

• Arbeiten von Zhao & Sun zur informationstheoretischen Secure Aggregation
• Kapazitätsergebnisse von Sun & Jafar zu Private Information Retrieval und Private Computation
• Symmetrische private Polynomberechnungsschemata von Zhu et al.
• Klassische informationstheoretische Sicherheitsergebnisse von Shannon

Gesamtbewertung: Dies ist ein hochqualitatives theoretisches Paper, das wichtige Beiträge im Schnittstellenbereich von Secure Aggregation und datenschutzgerechter Berechnung leistet. Obwohl es noch Verbesserungspotenzial in der Praktikabilität gibt, legen seine theoretischen Innovationen und strenge Analyse eine solide Grundlage für zukünftige Forschung.