2025-11-23T13:58:16.869352

Multi-Message Secure Aggregation with Demand Privacy

Sun, Zhang, Wan et al.

This paper considers a multi-message secure aggregation with privacy problem, in which a server aims to compute $\sf K_c\geq 1$ linear combinations of local inputs from $\sf K$ distributed users. The problem addresses two tasks: (1) security, ensuring that the server can only obtain the desired linear combinations without any else information about the users' inputs, and (2) privacy, preventing users from learning about the server's computation task. In addition, the effect of user dropouts is considered, where at most $\sf{K-U}$ users can drop out and the identity of these users cannot be predicted in advance. We propose two schemes for $\sf K_c$ is equal to (1) and $\sf 2\leq K_c\leq U-1$, respectively. For $\sf K_c$ is equal to (1), we introduce multiplicative encryption of the server's demand using a random variable, where users share coded keys offline and transmit masked models in the first round, followed by aggregated coded keys in the second round for task recovery. For $\sf{2\leq K_c \leq U-1}$, we use robust symmetric private computation to recover linear combinations of keys in the second round. The objective is to minimize the number of symbols sent by each user during the two rounds. Our proposed schemes have achieved the optimal rate region when $ \sf K_c $ is equal to (1) and the order optimal rate (within 2) when $\sf{2\leq K_c \leq U-1}$.

academic

Agrégation Sécurisée Multi-Messages avec Confidentialité des Demandes

Informations Fondamentales

ID de l'article: 2504.20639
Titre: Multi-Message Secure Aggregation with Demand Privacy
Auteurs: Chenyi Sun, Ziting Zhang, Kai Wan (Université de Technologie de Huazhong), Giuseppe Caire (Université Technique de Berlin)
Classification: cs.IT math.IT
Date de publication: 13 octobre 2025 (arXiv v2)
Lien de l'article: https://arxiv.org/abs/2504.20639

Résumé

Cet article étudie un problème d'agrégation sécurisée multi-messages avec confidentialité des demandes, où un serveur vise à calculer Kc≥1 combinaisons linéaires des entrées locales de K utilisateurs distribués. Le problème traite deux tâches : (1) la sécurité, garantissant que le serveur n'obtient que les combinaisons linéaires requises sans révéler d'autres informations sur les entrées des utilisateurs ; (2) la confidentialité, empêchant les utilisateurs de connaître les tâches de calcul du serveur. De plus, l'impact des déconnexions d'utilisateurs est considéré, avec au maximum K-U utilisateurs pouvant se déconnecter avec des identités imprévisibles. Les auteurs proposent deux schémas distincts pour les cas Kc=1 et 2≤Kc<U. Pour Kc=1, une méthode de chiffrement multiplicatif des demandes du serveur utilisant des variables aléatoires est introduite ; pour 2≤Kc<U, le calcul privé symétrique robuste est utilisé pour récupérer les combinaisons linéaires de clés dans la deuxième ronde.

Contexte et Motivation de la Recherche

Définition du Problème

L'apprentissage fédéré permet aux utilisateurs distribués de collaborer à l'entraînement d'un modèle global sous la coordination d'un serveur central, mais les mises à jour du modèle peuvent toujours révéler des informations sur les données locales des utilisateurs. Pour renforcer davantage la sécurité, l'agrégation sécurisée a été introduite pour garantir que le serveur n'obtient que les mises à jour agrégées sans aucune information supplémentaire sur les données des utilisateurs.

Motivation de la Recherche

Besoins d'apprentissage multi-tâches : Comparé à l'apprentissage mono-tâche, l'apprentissage multi-tâches peut exploiter plusieurs résultats pour améliorer les performances globales de l'entraînement du modèle, en augmentant l'efficacité d'apprentissage par le partage d'informations et de ressources.
Limitations des méthodes existantes :
- Les problèmes d'agrégation sécurisée théorique-informationnelle existants se concentrent principalement sur le cas Kc=1
- Absence de considération pour la protection de la confidentialité des tâches de calcul du serveur
- Nécessité de garantir la sécurité et la confidentialité en cas de déconnexion d'utilisateurs
Besoins d'application pratique : Dans les scénarios réels d'apprentissage fédéré, le serveur peut avoir besoin de calculer plusieurs combinaisons linéaires différentes, tandis que les utilisateurs ne devraient pas connaître les besoins de calcul spécifiques du serveur.

Contributions Principales

Formalisation d'un nouveau problème : Première proposition d'un problème d'agrégation sécurisée multi-messages avec confidentialité des demandes, élargissant le champ d'étude de l'agrégation sécurisée traditionnelle.
Schéma optimal (Kc=1) : Proposition d'un schéma d'agrégation sécurisée combinant le chiffrement multiplicatif des demandes et le chiffrement additif du modèle, réalisant la région de débit de communication optimal, égale à la capacité du problème d'agrégation sécurisée sans contrainte de confidentialité.
Schéma quasi-optimal (2≤Kc<U) : Utilisation d'un schéma de calcul privé symétrique, améliorant significativement la méthode de base consistant à répéter le premier schéma Kc fois, avec débit optimal à la première ronde et débit quasi-optimal à la deuxième ronde (dans un facteur 2).
Analyse théorique : Fourniture de preuves complètes d'accessibilité et d'analyse des bornes inverses, établissant les fondations théoriques du problème.

Détails de la Méthode

Modèle Système

Participants :

1 serveur et K utilisateurs non-collusifs (K≥2)
L'utilisateur i détient un vecteur d'entrée Wi et une clé Pi
Wi contient L symboles indépendants et identiquement distribués uniformément, définis sur le corps fini Fq

Fonction Objectif : Le serveur calcule la transformation linéaire : $g(W_1, \cdots, W_K) = F[W_1, \cdots, W_K]^T$

où F est une matrice de coefficients de dimension Kc×K :

a_{1,1} & \cdots & a_{1,K} \\ \vdots & \ddots & \vdots \\ a_{K_c,1} & \cdots & a_{K_c,K} \end{pmatrix}$$ **Modèle de Communication** : - **Première ronde** : Le serveur envoie la requête Q1,i à l'utilisateur i, l'utilisateur i retourne le message Xi - **Deuxième ronde** : Le serveur informe l'ensemble des utilisateurs actifs U1, envoie la requête Q^{U1}_{2,i}, l'utilisateur i envoie Y^{U1}_i ### Contraintes 1. **Décodabilité** : Le serveur peut calculer sans erreur les combinaisons linéaires requises 2. **Sécurité** : Le serveur ne peut pas obtenir d'informations sur les entrées des utilisateurs au-delà du résultat de calcul cible 3. **Confidentialité** : Les utilisateurs ne peuvent pas déduire la matrice de demande F du serveur ### Schéma pour le Cas Kc=1 #### Idée Centrale Combinaison du chiffrement multiplicatif des demandes et du chiffrement additif du modèle, en chiffrant les demandes du serveur via une variable aléatoire t. #### Étapes Détaillées **Phase 1 (Génération de Requête)** : - Le serveur choisit aléatoirement t ∈ Fq\{0} - Définit la requête : $Q_{1,i} = \frac{1}{ta_{1,i}}$, i ∈ [K] **Phase 2 (Génération de Clé)** : - Pour chaque utilisateur i, générer Zi uniformément distribué sur F^L_q - Diviser Zi en U sous-clés : [Zi]m ∈ F^{L/U}_q - Utiliser une matrice MDS M pour coder : $[\tilde{Z}_i]_j = ([Z_i]_1, \ldots, [Z_i]_U) \cdot M_{:,j}$ **Phase 3 (Transmission de Première Ronde)** : - L'utilisateur i envoie : $X_i = W_i + Q_{1,i}Z_i$ **Phase 4 (Transmission de Deuxième Ronde)** : - L'utilisateur j ∈ U1 envoie les sous-clés codées agrégées : $\sum_{i \in U_1}[\tilde{Z}_i]_j$ - Le serveur récupère $\sum_{i \in U_1} Z_i$ par décodage MDS #### Processus de Déchiffrement Le serveur calcule : $$\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$$ Puisque $t \sum_{i \in U_1} a_{1,i}W_i = \sum_{i \in U_1} \frac{1}{Q_{1,i}}W_i$, le serveur peut décoder la combinaison linéaire cible. ### Schéma pour le Cas 2≤Kc<U #### Idée Centrale Utilisation du calcul privé symétrique robuste pour garantir la sécurité et la confidentialité lors de la transmission de deuxième ronde. #### Étapes Détaillées **Phase 1 (Génération de Clé)** : - Pour chaque i ∈ [K], choisir aléatoirement Zi de F^L_q - Tous les utilisateurs partagent la clé : Pi = (Zi)i∈[K] - Partager L/(U-1) variables aléatoires publiques comme masques de clé **Phase 2 (Transmission de Première Ronde)** : - L'utilisateur i envoie : $X_i = W_i + Z_i$ **Phase 3 (Transmission de Deuxième Ronde)** : - Le serveur doit récupérer Kc combinaisons de clés : $\sum_{i \in U_1} a_{n,i}Z_i$, n ∈ [Kc] - Diviser chaque clé Zi en sous-clés de longueur L' = U-1 - Utiliser le schéma de calcul privé symétrique Kc fois, obtenant respectivement chaque combinaison linéaire - Construire des polynômes de requête via codage de Lagrange pour protéger la confidentialité des tâches de calcul ## Résultats Expérimentaux ### Résultats Théoriques **Théorème 3 (Optimalité pour Kc=1)** : Pour le problème d'agrégation sécurisée multi-messages (K,U,Kc), lorsque U≤K-1 et Kc=1, la région de capacité est : $$\mathcal{R}^* = \{(R_1,R_2) : R_1 \geq 1, R_2 \geq \frac{1}{U}\}$$ **Théorème 5 (Accessibilité pour 2≤Kc<U)** : Lorsque 2≤Kc<U≤K-1, le tuple de débit $(R_1 = 1, R_2 = \frac{K_c}{U-1})$ est accessible. **Théorème 6 (Borne Inverse)** : Tout débit accessible doit satisfaire : $R_1 \geq 1, R_2 \geq \frac{K_c}{U}$ ### Analyse de Performance 1. **Optimalité** : Le cas Kc=1 atteint l'optimum théorique 2. **Quasi-optimalité** : Pour le cas 2≤Kc<U, le débit de première ronde est optimal, le débit de deuxième ronde est quasi-optimal dans un facteur 2 : $$\frac{K_c/(U-1)}{K_c/U} = \frac{U}{U-1} \leq 2$$ 3. **Comparaison avec la Méthode de Base** : Comparé au schéma de répétition directe, le nouveau schéma réduit le débit de première ronde de Kc à 1, et augmente le débit de deuxième ronde de Kc/U à Kc/(U-1) ## Travaux Connexes ### Agrégation Sécurisée - **Agrégation sécurisée théorique-informationnelle** : Zhao et Sun ont d'abord proposé une formalisation théorique-informationnelle, réalisant la région de capacité {(R1,R2) : R1≥1, R2≥1/U} - **Agrégation sécurisée pratique** : LightSecAgg réduit considérablement le nombre de clés requises en découplant le processus de génération de clés ### Récupération et Calcul Privés d'Informations - **Récupération Privée d'Informations (PIR)** : Permet au serveur de récupérer privément des messages d'une base de données distribuée - **Calcul Privé (PC)** : Étend le cadre PIR pour inclure les calculs linéaires sur les messages - **Calcul Privé Symétrique** : Protège simultanément la confidentialité des tâches de calcul du serveur et la sécurité des données des utilisateurs ### Apprentissage Multi-Tâches - **Apprentissage Coordonné** : Plusieurs tâches collaborent par le partage d'informations et de ressources, améliorant l'efficacité globale d'apprentissage - **Représentation Commune** : Les tâches bénéficient de représentations communes, de gradients ou de composants partagés ## Conclusion et Discussion ### Conclusions Principales 1. Première formalisation du problème d'agrégation sécurisée multi-messages avec confidentialité des demandes 2. Réalisation de la région de débit de communication optimal pour Kc=1 3. Réalisation de performances optimales à la première ronde et quasi-optimales à la deuxième ronde pour 2≤Kc<U 4. Fourniture d'un cadre d'analyse théorique complet ### Limitations 1. **Région Ouverte** : La caractérisation de la région de capacité pour Kc≥U reste non résolue 2. **Taille de Clé** : Optimisation non effectuée de la minimisation de la taille de clé requise 3. **Praticité** : La complexité de mise en œuvre des schémas théoriques dans les systèmes réels est élevée 4. **Extensibilité** : Extensibilité limitée aux tâches de calcul non-linéaires ### Directions Futures 1. **Caractérisation Complète de la Région de Capacité** : Résoudre le problème d'optimalité pour le cas Kc≥U 2. **Optimisation de Clé** : Minimiser la taille de clé requise pour améliorer la praticité 3. **Implémentation Système** : Développer des prototypes de systèmes réellement déployables 4. **Extension Non-Linéaire** : Étendre aux tâches de calcul non-linéaires ## Évaluation Approfondie ### Points Forts 1. **Contribution Théorique Significative** : Combinaison pionnière de l'agrégation sécurisée et de la confidentialité des demandes, comblant un vide théorique important 2. **Forte Innovativité Méthodologique** : Combinaison ingénieuse du chiffrement multiplicatif et du calcul privé symétrique, approche technique novatrice 3. **Analyse Théorique Complète** : Fourniture de preuves rigoureuses d'accessibilité et d'analyse des bornes inverses 4. **Importance Pratique Significative** : Résolution d'un problème important de protection de la confidentialité dans l'apprentissage fédéré ### Insuffisances 1. **Champ d'Application Limité** : Considération uniquement des tâches de calcul linéaires, les applications réelles peuvent nécessiter des opérations non-linéaires 2. **Complexité de Mise en Œuvre Élevée** : Particulièrement pour le cas 2≤Kc<U, la mise en œuvre du calcul privé symétrique est relativement complexe 3. **Restrictions de Paramètres** : La restriction Kc<U peut être trop stricte dans certains scénarios d'application 4. **Absence de Vérification Expérimentale** : Manque de mise en œuvre de système réel et de tests de performance ### Influence 1. **Valeur Académique** : Fourniture d'un nouveau cadre théorique pour le calcul multi-parties sécurisé et le domaine de l'apprentissage fédéré 2. **Potentiel Pratique** : Fourniture de fondations théoriques pour l'apprentissage automatique distribué avec protection de la confidentialité 3. **Reproductibilité** : Les résultats théoriques sont clairs, mais la mise en œuvre réelle nécessite un travail d'ingénierie considérable ### Scénarios d'Application 1. **Apprentissage Fédéré** : Agrégation avec protection de la confidentialité dans l'apprentissage fédéré multi-tâches 2. **Statistiques Distribuées** : Systèmes distribués nécessitant le calcul de plusieurs statistiques 3. **Analyse avec Protection de la Confidentialité** : Scénarios d'analyse de données dans les secteurs financier, médical et autres domaines exigeant une protection stricte de la confidentialité ## Références L'article cite plusieurs références importantes, notamment : - Les travaux sur l'agrégation sécurisée théorique-informationnelle de Zhao & Sun - Les résultats sur la capacité de récupération privée d'informations et de calcul privé de Sun & Jafar - Le schéma de calcul privé polynomial symétrique de Zhu et al. - Les résultats classiques de sécurité théorique-informationnelle de Shannon --- **Évaluation Globale** : Ceci est un article théorique de haute qualité qui apporte des contributions importantes au domaine d'intersection entre l'agrégation sécurisée et le calcul avec protection de la confidentialité. Bien qu'il y ait encore de la place pour amélioration en termes de praticité, son innovation théorique et son analyse rigoureuse établissent une base solide pour les recherches futures.