Résumé Technique : Giskard

Problématique

L'apprentissage décentralisé offre une alternative respectueuse de la vie privée à l'entraînement centralisé en permettant aux participants d'interagir en pair à pair sans orchestrateur central de confiance. Cependant, ces systèmes sont confrontés à deux défis simultanés et souvent conflictuels :

1. Robustesse Byzantine : Des nœuds malveillants ou défaillants peuvent soumettre des mises à jour de modèles arbitraires et manipulées (empoisonnement de modèle) pour corrompre le modèle global. La défense contre cela nécessite généralement l'inspection et la comparaison des contributions individuelles pour filtrer les valeurs aberrantes (par exemple, en utilisant des médianes par coordonnée ou des moyennes tronquées).
2. Confidentialité : Les participants doivent préserver la confidentialité de leurs données locales et de leurs mises à jour de modèles. Les techniques cryptographiques comme le calcul multipartite sécurisé (MPC) masquent ces mises à jour, mais les fonctions d'agrégation robuste standard (qui reposent sur le tri et la comparaison) sont coûteuses à implémenter sous forme chiffrée.

Les solutions existantes traitent ces problèmes séparément ou les combinent en utilisant le MPC de manières qui ne passent pas à l'échelle. Les approches MPC décentralisées antérieures reposent souvent sur une communication de type "all-to-all" (tout vers tous) ou délèguent le calcul à un petit comité unique, ce qui entraîne une complexité de communication par nœud qui croît linéairement ou plus ($O(n)$ ou $O(n \log^2 n)$). Cela crée un goulot d'étranglement fondamental pour la scalabilité dans les déploiements à grande échelle (par exemple, $n \ge 10^4$).

Méthodologie : Le Protocole Giskard

Giskard est un protocole conçu pour atteindre à la fois la robustesse Byzantine et la confidentialité dans un environnement entièrement décentralisé avec une complexité de communication sous-linéaire. Il opère sous un modèle d'adversaire statique et aux capacités de calcul limitées, où jusqu'à $f < n/4$ parties peuvent être corrompues.

Concepts Techniques Clés

1. Recherche Binaire pour la Médiane : Au lieu d'implémenter des circuits de tri génériques (qui sont coûteux en MPC), Giskard reformule le calcul de la médiane par coordonnée sous la forme d'une recherche binaire sécurisée sur le domaine des valeurs. Le protocole réduit itérativement l'intervalle $[Gauche, Droite]$ en comptant combien d'entrées sont inférieures à un pivot $p_t$. Cela réduit le problème à une séquence d'opérations de comptage sécurisées.
2. Arbre de Comités Hiérarchique : Pour distribuer la charge de calcul, Giskard organise $n$ parties en un arbre de comités $k$-aire, chaque comité ayant une taille $m = O(\log n)$.
   • Feuilles (Niveau 0) : Les parties individuelles comparent leurs vecteurs locaux au pivot actuel et partagent secrètement les vecteurs de bits résultants avec leurs comités de base assignés.
   • Comités de Base (Niveau 1) : Valident le domaine des bits partagés (s'assurant qu'ils sont de 0 ou 1) à l'aide d'une preuve de degré 2, agrègent les parts, et repartagent les sommes partielles vers le haut.
   • Comités Intermédiaires (Niveaux 2 à $L-1$) : Reçoivent les parts des comités enfants, effectuent un repartage vérifiable, et agrègent vers le haut.
   • Comité Racine (Niveau $L$) : Reconstruit le compte global en clair, met à jour le pivot, et diffuse le nouveau pivot vers le bas de l'arbre pour l'itération suivante.
3. Primitives Cryptographiques : Le protocole utilise le partage de secret vérifiable (VSS) basé sur le schéma BGW (Asharov et Lindell) pour garantir la sécurité contre les adversaires malveillants. Il emploie des sous-protocoles pour le partage, la multiplication et le repartage, tous prouvés comme étant sécurisés selon le modèle de composition universelle (UC).

Garanties de Sécurité et de Robustesse

• Confidentialité : Les entrées individuelles et les comptes intermédiaires restent cachés ; seul le compte agrégé final (utilisé pour mettre à jour le pivot) est révélé.
• Robustesse Byzantine : Le protocole tolère jusqu'à $n/4$ parties Byzantines. Il satisfait le critère de robustesse Byzantine $(f, \kappa)$, garantissant que la sortie reste proche de la moyenne des mises à jour honnêtes, correspondant au seuil de robustesse de la médiane par coordonnée.
• Correction : La recherche binaire converge vers la médiane avec une précision $q$ après $N_{iter} = \lceil \log_2(2u/q) \rceil$ itérations.

Principales Contributions

1. Protocole Novateur : Proposition de Giskard, un protocole d'apprentissage décentralisé robuste et confidentiel capable de passer à l'échelle pour des millions de parties.
2. Sécurité Théorique : Une preuve formelle que Giskard est UC-sécurisé dans le modèle hybride, s'appuyant sur des hypothèses cryptographiques standards et la sécurité de ses sous-protocoles (BA, VSS, etc.).
3. Analyse de la Complexité de Communication : Démonstration que la complexité de communication par partie dans le pire des cas est polylogarithmique en $n$ ($O(d \cdot N_{iter} \cdot \log^3 n)$), une amélioration significative par rapport aux concurrents comme le All-to-All ($O(d \cdot n^2)$) ou le All-to-Committee ($O(d \cdot n \log^2 n)$).
4. Validation Expérimentale : Évaluation approfondie sur les jeux de données MNIST et CIFAR-10 avec des tailles de réseau allant jusqu'à $n=10^6$.

Résultats Expérimentaux

Les auteurs ont évalué Giskard par rapport à deux topologies de référence : All-to-All (A2A) et All-to-Committee (A2C).

• Scalabilité (Coût de Communication) :

  • À $n=10^6$ avec une fraction Byzantine de 10 %, Giskard réduit la communication par partie d'environ 1 775 fois par rapport à A2C et de plusieurs ordres de grandeur par rapport à A2A.
  • Alors que l'A2C concentre la charge sur un seul comité (ce qui le rend impraticable à cause des limites de bande passante à grande échelle), Giskard distribue la charge à travers l'arbre, maintenant les coûts par partie gérables même pour $n=10^6$.
  • Le temps d'exécution estimé pour A2C et A2A à grande échelle dépasse les limites pratiques (jours à années), tandis que Giskard reste dans l'ordre de quelques minutes à quelques heures.

• Utilité du Modèle (Robustesse) :

  • Sous quatre attaques d'empoisonnement de modèle (Label Flipping, Sign Flipping, IPM, ALIE) sur des données non-i.i.d., la médiane par recherche binaire de Giskard a atteint une précision de test comparable aux agrégateurs robustes en texte clair de pointe (Trimmed Mean, Median).
  • Sur MNIST, l'écart de précision était inférieur à 0,4 %. Sur CIFAR-10, l'écart était généralement inférieur à 1,5 %, avec des écarts légèrement plus élevés (jusqu'à 2,7 %) pour des attaques hautement optimisées nécessitant une plus grande précision.
  • Les expériences ont identifié un seuil critique pour le nombre d'itérations de la recherche binaire ($N_{iter}$) ; augmenter les itérations au-delà d'environ 10 n'apportait aucun gain de robustesse significatif mais augmentait linéairement les coûts de communication.

Signification et Revendications

L'article affirme que Giskard comble le fossé entre la scalabilité et la sécurité dans l'apprentissage décentralisé. En combinant une structure de comité hiérarchique avec une formulation spécialisée de la médiane par recherche binaire, Giskard atteint :

• Une communication sous-linéaire : C'est le premier protocole à atteindre une communication par partie polylogarithmique pour l'agrégation robuste et confidentielle dans un cadre entièrement décentralisé.
• Des Garanties Formelles : Contrairement aux approches heuristiques, Giskard fournit des preuves de sécurité UC et des bornes de robustesse formelles.
• Praticité : Les résultats expérimentaux démontrent que le protocole est viable pour des déploiements à grande échelle (jusqu'à un million de participants) là où les solutions MPC précédentes seraient informatiquement et communicativement infaisables.

Les auteurs concluent que bien que le protocole introduise un compromis entre le nombre d'itérations et la précision, le système proposé équilibre efficacement la confidentialité, la robustesse et la scalabilité, rendant l'apprentissage décentralisé sécurisé à grande échelle pratique. Des travaux futurs sont suggérés pour explorer des variantes computationnelles basées sur des hypothèses cryptographiques afin de réduire davantage les coûts.