Résumé Technique : NFSA : Agrégation non sécurisée vers l'avant avec un serveur unique via un partage de secret à deux couches

1. Énoncé du Problème

L'apprentissage fédéré (Federated Learning - FL) permet l'entraînement collaboratif de modèles tout en gardant les données locales, mais la transmission des mises à jour de modèles (gradients) pose toujours des risques pour la confidentialité. Des protocoles d'agrégation sécurisée sont nécessaires pour garantir que le serveur n'apprenne que le modèle agrégé, et non les entrées individuelles des utilisateurs.

Les protocoles d'agrégation sécurisée basés sur un serveur font face à deux défis principaux, particulièrement dans les scénarios trans-appareils (cross-device) :

1. Abandon d'utilisateur et transfert de clés : Pour gérer l'abandon des utilisateurs (dropouts), les protocoles utilisent souvent le partage de secret (Secret Sharing - SS) à seuil, tel que le SS de Shamir, où les utilisateurs partagent des clés secrètes avec des "détenteurs" (autres utilisateurs ou comités). Dans les configurations à serveur unique, les utilisateurs ne peuvent pas communiquer directement ; ainsi, le serveur doit donc transférer ces parts de secret. Ce transfert introduit une surcharge de communication importante ($O(NM)$ par round, où $N$ est le nombre d'utilisateurs et $M$ le nombre de détenteurs) et des risques de sécurité, car le serveur doit être fiable pour ne pas altérer ou apprendre les parts transférées (ce qui nécessite souvent un chiffrement authentifié).
2. Efficacité de la communication : Les paramètres de modèles de haute dimension et le grand nombre d'utilisateurs créent des goulots d'étrangleux de bande passante. Les schémas récents d'agrégation "en un seul coup" (one-shot) utilisant des Fonctions Pseudo-Aléatoires Homomorphes de Clé (KhPRF) réduisent les cycles d'interaction mais souffrent d'une "expansion de ciphertext". L'Almost KhPRF (basée sur LWR/LWE) introduit un bruit proportionnel au nombre d'utilisateurs, nécessitant un espace supplémentaire dans les mises à jour du modèle pour éviter les interférences, ce qui augmente le volume total de communication ($O(RN \log N)$).

2. Méthodologie

Le papier propose NFSA (Non-Forward Secure Aggregation), un protocole conçu pour un scénario de FL à serveur unique qui élimine la nécessité pour le serveur de transférer des données secrètes et réduit la surcharge de communication grâce à une nouvelle méthode de codage.

2.1 Partage de Secret à Deux Couches (TLSS)

Pour résoudre le problème de transfert, les auteurs introduisent le TLSS, qui combine deux couches de partage de secret pour permettre une agrégation sécurisée sans relais de parts sensibles par le serveur :

• Couche 1 (SS à seuil) : Utilise le partage de secret de Shamir pour gérer l'abandon des utilisateurs. Le secret d'un utilisateur (par exemple, une clé KhPRF) est divisé en parts $s_m$ distribuées à $M$ détenteurs.
• Couche 2 (SS Additif avec PRF) : Au lieu d'envoyer $s_m$ directement au serveur pour transfert, l'utilisateur divise $s_m$ en deux parts additives : $s_m = s_{m}^{A1} + s_{m}^{A2} \mod p$.
  • $s_{m}^{A1}$ est généré à l'aide d'une Fonction Pseudo-Aléatoire (PRF) indexée par une clé partagée pré-négociée $\kappa_{d,m}$ entre l'utilisateur et le détenteur $P_m$.
  • $s_{m}^{A2}$ est calculé comme $s_{m}^{A2} = s_m - s_{m}^{A1} \mod p$.
  • L'utilisateur envoie uniquement $s_{m}^{A2}$ au serveur.
  • Le serveur envoie un tag au détenteur $P_m$, qui calcule $s_{m}^{A1}$ en utilisant sa clé partagée et le renvoie au serveur.
  • Le serveur reconstruit $s_m = s_{m}^{A1} + s_{m}^{A2}$ et procède à la reconstruction de Shamir.
• Résultat : Le serveur ne transfère jamais de parts de secret entre les utilisateurs et les détenteurs, éliminant ainsi la surcharge de transfert $O(NM)$ et l'exigence de chiffrement authentifié sur les parts.

2.2 Codage CRT pour l'Almost KhPRF

Pour résoudre l'expansion de la communication causée par le bruit de l'Almost KhPRF, les auteurs proposent une nouvelle méthode de codage basée sur le Théorème des Restes Chinois (CRT) :

• Problème : Les méthodes existantes masquent les entrées $x_i$ sous la forme $y_i = \Delta x_i - F(k_i, \tau)$. Pour décoder correctement, $\Delta$ doit être plus grand que le nombre d'utilisateurs $n$, augmentant la longueur en bits de chaque élément de $\log_2(n+1)$.
• Solution : Les auteurs emballent $d_c$ éléments du vecteur d'entrée dans un seul entier en utilisant le CRT.
  • Les éléments d'entrée sont étendus à des modules premiers distincts $p_i$.
  • Ceux-ci sont combinés en un seul élément dans $\mathbb{Z}_{p_c}$ (où $p_c = \prod p_i$).
  • L'agrégation masquée est effectuée sur ces éléments emballés.
• Bénéfice : Cela réduit le nombre d'appels à la KhPRF d'un facteur $d_c$ et réduit considérablement le volume total de communication en évitant l'expansion par élément du $\Delta$.

2.3 Le Protocole NFSA

Le protocole opère en deux phases :

1. Phase Hors-ligne (Offline) : Les utilisateurs et les déchiffreurs (détenteurs) effectuent un Accord de Clé (KA) pour établir des clés partagées. Cette phase est sans état (stateless) et n'est effectuée qu'une seule fois.
2. Phase En-ligne (Online - One-Shot) :
   • Masquage : Chaque utilisateur génère une clé KhPRF, la partage via TLSS (en envoyant uniquement les parts additives au serveur), et masque sa mise à jour de modèle en utilisant la KhPRF emballée par CRT.
   • Démasquage : Les déchciteurs calculent la somme de leurs parts additives (en exploitant l'homomorphisme du TLSS) et les envoient au serveur. Le serveur reconstruit la clé KhPRF globale, génère le masque global, et démasque le ciphertext agrégé pour récupérer la mise à jour du modèle.

3. Contributions Clés

1. Schéma TLSS : Un nouveau schéma de partage de secret à deux couches qui élimine la nécessité pour un serveur de transférer des parts de secret dans un contexte de FL à serveur unique. Il réduit la surcharge de communication pour le partage de clés et supprime l'exigence de chiffrement authentifié sur les données transférées.
2. Codage CRT pour l'Almost KhPRF : Une nouvelle méthode de codage d'entrée qui utilise le Théorème des Restes Chinois pour regrouper (batch) plusieurs entrées. Cela réduit le nombre d'appels à la KhPRF et atténue le problème d'expansion de la mise à jour du modèle causé par le bruit de l'Almost KhPRF, diminuant ainsi les surcharges de calcul et de communication.
3. Protocole NFSA : Un protocole d'agrégation sécurisée compact et "one-shot" combinant le TLSS et le codage CRT. Il supporte l'agrégation de données de haute dimension avec un serveur unique et sans transfert de données intermédiaire.

4. Résultats Expérimentaux

Les auteurs ont implémenté le protocole en Python et l'ont comparé au schéma de pointe OPA (qui utilise le SS de Shamir et la KhPRF sans TLSS ni emballage CRT).

• Performance TLSS : Comparé au SS de Shamir traditionnel avec transfert, le TLSS a réduit la surcharge de communication des détenteurs d'environ 57 % et le temps de calcul de 95 % (pour un module de 64 bits) lors du partage de secrets avec 50 détenteurs. La surcharge totale était nettement inférieure grâce à l'élimination du transfert par le serveur.
• Performance du Codage CRT : L'utilisation de l'emballage CRT ($d_c=4$) a réduit le temps de masquage de l'utilisateur de 3,72× et le trafic de communication de 1,40× par rapport à OPA.
• Performance End-to-End de NFSA :
  • Surcharge Utilisateur : Pour 100 utilisateurs, NFSA a amélioré l'efficacité de la communication de près de 100 fois (spécifiquement pour la communication des déchiffreurs) et a réduit le temps de calcul de l'utilisateur de 51 % à 75 % (selon la longueur de l'entrée).
  • Surcharge Serveur : Le temps de calcul du serveur a été réduit d'environ 50 %, et le trafic de communication du serveur a été réduit de 25 % par rapport à OPA.
  • Surcharge Déchiffreur : La communication du déchiffreur est passée d'environ 19 Mo (OPA) à environ 0,19 Mo (NFSA), soit une réduction de près de 100 fois.

5. Signification et Revendications

Le papier affirme que NFSA résout le goulot d'étranglement critique du transfert par le serveur dans l'agrégation sécurisée à serveur unique. En découplant le processus de partage de secret du rôle de relais du serveur, il réduit considérablement la surface d'attaque et les coûts de communication. L'intégration du codage CRT optimise davantage l'efficacité de l'Almost KhPRF, la rendant viable pour les modèles de FL de haute dimension.

Les auteurs positionnent NFSA comme une solution hautement efficace pour les environnements semi-honnêtes (semi-honest). Ils reconnaissent que si OPA offre des garanties plus fortes dans les contextes malveillants (via des mécanismes de vérification comme SCRAPE et ZKP), NFSA atteint une efficacité supérieure dans le modèle semi-honnête. Le travail suggère que NFSA est évolutif et pratique pour les applications de FL réelles, bien que des travaux futurs soient nécessaires pour étendre sa vérifiabilité aux contextes malveillants et affiner la vérification des entrées emballées par CRT.