Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning

Cet article propose des algorithmes de multiplication de matrices creuses sécurisées par calcul multipartite (MPC) qui surmontent les limitations de mémoire et réduisent considérablement les coûts de communication par rapport aux méthodes denses, permettant ainsi l'application du machine learning préservant la vie privée sur des données réelles de grande dimension.

L'essentiel

Imaginez que vous voulez organiser une grande fête (l'apprentissage automatique) où chaque invité apporte un plat secret (vos données privées). Le problème, c'est que dans le monde de la cryptographie moderne, on ne peut pas ouvrir les plats pour les mélanger sans révéler ce qu'il y a dedans. C'est là qu'intervient le Calcul Multi-Parties (MPC) : une technique magique qui permet de cuisiner ensemble sans jamais voir les ingrédients des autres.

Cependant, il y a un gros problème avec les méthodes actuelles : elles sont conçues pour des plats "denses" (comme une tourte remplie à ras bord). Mais dans la vraie vie, la plupart des données ressemblent à une tourte où 99 % de l'espace est vide (des trous !). C'est ce qu'on appelle des données "creuses" (sparse).

Voici comment Marc Damie et son équipe ont résolu ce casse-tête, expliqué simplement :

1. Le Problème : Remplir l'océan avec des gouttes d'eau

Dans des applications comme les recommandations de films (Netflix) ou la génétique, les données sont immenses mais presque toutes vides.

• L'approche classique (Dense) : Imaginez que vous devez stocker un livre entier sur une étagère, mais que le livre contient 99 % de pages blanches. La méthode classique vous oblige à acheter une étagère géante pour tout le livre, même si vous n'avez que quelques lignes d'écriture. En cryptographie, cela consomme une mémoire énorme (des téraoctets !) et coûte très cher en communications entre les serveurs. C'est comme essayer de transporter un océan juste pour déplacer une goutte d'eau.
• La conséquence : Les systèmes de confidentialité actuels échouent sur ces données car ils manquent de place ou deviennent trop lents.

2. La Solution : Le "Filtre Magique"

Les auteurs ont créé de nouveaux algorithmes spécialisés pour les données "creuses". Au lieu de transporter tout le livre (pages blanches incluses), ils ne transportent que les lignes écrites.

Ils utilisent une astuce intelligente basée sur le tri :

1. Le Tri Silencieux : Imaginez que chaque serveur a une liste de ses ingrédients secrets. Au lieu de les mélanger au hasard, ils les trient "silencieusement" (personne ne voit qui a apporté quoi, juste l'ordre).
2. L'Assemblage : Une fois triés, ils ne gardent que les ingrédients qui se correspondent (par exemple, "Tomate" avec "Tomate"). Tout ce qui est vide (les pages blanches) est ignoré instantanément.
3. Le Résultat : Au lieu de faire des milliards de calculs inutiles sur des zéros, ils ne font que les calculs nécessaires.

L'analogie du tri : C'est comme si vous deviez trouver des paires de chaussettes dans un tas de 10 000 chaussettes, mais 9 900 sont manquantes. La méthode classique fouillerait chaque trou. La nouvelle méthode trie les chaussettes par couleur et taille, et ne regarde que les rares paires qui existent.

3. Les Résultats : Une économie folle

Grâce à cette méthode, les auteurs ont obtenu des résultats spectaculaires :

• Mémoire : Au lieu de nécessiter 19 Téraoctets (comme une bibliothèque entière), leur méthode n'en demande que 60 Gigaoctets (comme quelques DVD).
• Vitesse et Coût : Ils ont réduit les échanges de données entre les serveurs par un facteur de 1000. C'est comme passer d'un camion-citerne à une bicyclette pour livrer un message.
• Applications réelles : Ils ont testé cela sur deux cas concrets :
  • Un système de recommandation (comme Netflix) : trouver des films similaires sans jamais voir l'historique des utilisateurs.
  • Un système de contrôle d'accès : vérifier si une demande d'accès à un dossier médical est suspecte, sans révéler les données du patient.

4. Le Secret de la Confidentialité : "Combien de trous ?"

Pour que ce système fonctionne, les serveurs doivent savoir combien de données non-vides il y a par ligne (la "sparsité"), mais pas quelles sont ces données. C'est un peu comme savoir qu'il y a 5 pommes dans un panier, sans savoir où elles sont placées.

Si cette information est trop sensible, les auteurs proposent des astuces pour la protéger :

• Le "Masque" (Padding) : On ajoute de fausses données (des "pommes en plastique") pour que tout le monde ait le même nombre de données, rendant l'analyse impossible.
• Le "Moule" (Matrix Templating) : On crée un moule flexible basé sur des statistiques globales (ex: "la plupart des gens ont peu de données, quelques-uns en ont beaucoup") plutôt que de révéler les chiffres exacts de chaque personne.

En résumé

Cette recherche est une révolution pour la vie privée. Elle permet de faire de l'intelligence artificielle sur des données massives et vides (comme les réseaux sociaux ou la génétique) sans exploser les coûts de calcul ni révéler les secrets des utilisateurs.

C'est comme passer d'une méthode qui vide l'océan pour trouver un poisson, à une méthode qui utilise un filet intelligent pour attraper uniquement le poisson, en laissant l'eau couler à travers.

Résumé technique

1. Problématique

Le Calcul Multi-Parties (MPC) permet d'exécuter des algorithmes d'apprentissage automatique (ML) sur des données privées partagées entre plusieurs parties. Cependant, les frameworks MPC existants ne disposent pas d'opérations optimisées pour les données creuses (sparse data), c'est-à-dire des données contenant une majorité de zéros.

• Contexte : De nombreuses applications réelles (systèmes de recommandation, génomique, traitement du langage naturel) génèrent des données de très haute dimension et extrêmement creuses (ex: 99,99 % de zéros).
• Limites des approches actuelles :
  • Les algorithmes MPC actuels traitent les données sous forme denses (matrices complètes).
  • Pour des données réelles, le stockage dense devient prohibitif en termes de mémoire (ex: 19 To pour certaines matrices), rendant le calcul impossible.
  • Même si la mémoire était disponible, les coûts de communication et de calcul resteraient inefficaces car ils traitent tous les zéros inutilement.
• Défi spécifique : Les travaux précédents sur la multiplication de matrices creuses sécurisées nécessitent souvent que l'une des parties de calcul connaisse les données en clair (modèle non "outsourcé") ou ne supportent qu'un nombre limité de propriétaires de données. Or, les applications ML modernes nécessitent un modèle outsourcé où des milliers de propriétaires de données envoient leurs secrets à un groupe de serveurs de calcul qui les traitent sans les connaître en clair.

2. Méthodologie

Les auteurs proposent deux nouveaux algorithmes MPC pour multiplier des matrices creuses partagées secrètement (secret-shared), conçus spécifiquement pour le modèle outsourcé.

Représentation des données

• Utilisation du format COO (Coordinate) : chaque vecteur creux est représenté par une liste de tuples (coord, valeur) pour les éléments non nuls.
• Les algorithmes reposent sur des primitives MPC de base : additions, multiplications, comparaisons, tri aveugle (oblivious sorting) et mélange aveugle (oblivious shuffling).

Algorithmes Proposés

1. Multiplication Vecteur-Vecteur (Toy Protocol) :

   • Concaténation des listes de tuples des deux vecteurs.
   • Tri aveugle par coordonnées.
   • Multiplication des valeurs si les coordonnées correspondent, puis sommation.
   • Complexité : $O(N \log N)$ où $N$ est le nombre d'éléments non nuls.

2. Multiplication Matrice-Vecteur :

   • Évite la réplication inefficace du vecteur pour chaque ligne de la matrice.
   • Stratégie : Regrouper les éléments par colonne du vecteur et par ligne de la matrice, multiplier, puis agréger les résultats par coordonnées.
   • Utilisation de "placeholders" (valeurs fictives) pour gérer les structures de contrôle sans révéler de l'information, suivie d'un nettoyage via un mélange aveugle.

3. Multiplication Matrice-Matrice (ex: $X^T X$) :

   • Généralisation de l'approche précédente.
   • Calcul de toutes les multiplications scalaires individuelles entre les colonnes de la première matrice et les lignes de la seconde.
   • Agrégation des résultats via un tri aveugle et une somme conditionnelle.
   • La complexité dépend du nombre de multiplications scalaires non nulles ($MinMult$) plutôt que de la taille totale de la matrice.

Minimisation de la Connaissance Publique

Les algorithmes efficaces nécessitent de connaître la sparsité (nombre d'éléments non nuls par ligne/colonne). Pour préserver la vie privée, les auteurs proposent trois techniques pour minimiser cette information publique :

1. Anonymisation des lignes : Les propriétaires envoient leurs données via un réseau d'anonymisation (ex: Tor) pour cacher quel propriétaire correspond à quel nombre de non-zéros. Seule la distribution globale est connue.
2. Remplissage (Padding) maximal : On suppose un nombre maximal de non-zéros par ligne et on remplit toutes les lignes avec des "faux" non-zéros (dummy). Cela crée un surcoût mémoire important si la distribution est très inégale.
3. Modélisation par Template (Matrix Templating) : Technique innovante divisant la matrice en sous-matrices basées sur des quartiles de la distribution des non-zéros. Chaque sous-matrice est remplie jusqu'à un seuil spécifique. Cela réduit considérablement le nombre de faux non-zéros par rapport au remplissage global.

Des protocoles sont également proposés pour estimer ces templates de manière privée, soit via le MPC (estimation de quantiles), soit via la Différentielle Privée (DP) pour publier des bornes supérieures sûres sans révéler les données brutes.

3. Contributions Clés

• Algorithmes MPC pour données creuses : Première implémentation de multiplication matrice-vecteur et matrice-matrice sécurisée compatible avec un modèle outsourcé (nombre illimité de propriétaires de données).
• Réduction drastique des coûts :
  • Mémoire : Évite les débordements de mémoire (ex: passage de 19 To à 60 Go dans certains cas).
  • Communication : Réduction des coûts de communication jusqu'à un facteur 1000 par rapport aux méthodes denses pour des sparsités réalistes (99,99 %).
• Gestion de la confidentialité de la structure : Proposition de techniques pour minimiser la connaissance publique nécessaire (sparsité) tout en maintenant l'efficacité, via l'anonymisation, le padding et le templating.
• Validation pratique : Implémentation de deux applications ML réelles (système de recommandation et contrôle d'accès) qui sont impossibles à exécuter avec des méthodes denses existantes.

4. Résultats Expérimentaux

Les expériences ont été menées sur un serveur avec 188 Go de RAM en simulant un protocole à 3 parties (majorité honnête) avec le framework MPyC.

• Comparaison Densité vs Creux :
  • Pour des matrices de 10 000 colonnes avec 99,99 % de sparsité, l'algorithme dense provoque un débordement de mémoire (nécessiterait ~19 To), tandis que l'algorithme creux fonctionne.
  • Réduction de communication : facteur 100 pour 99,9 % de sparsité et facteur 1000 pour 99,99 % de sparsité.
• Cas d'usage 1 : Système de recommandation (Bookcrossing)
  • Dataset : 279k utilisateurs, 340k livres (99,998 % de zéros).
  • Résultat : L'algorithme dense échoue par manque de mémoire. L'algorithme creux exécute l'inférence en ~48 minutes.
• Cas d'usage 2 : Contrôle d'accès (Amazon Access Control)
  • Dataset : 32,7k échantillons, 15k features (99,95 % de zéros).
  • Tâche : Estimation de la matrice de covariance pour une analyse discriminante linéaire.
  • Résultat : L'algorithme dense échoue lors du calcul de la covariance. L'algorithme creux termine l'entraînement en 5 heures.
• Impact des techniques de minimisation :
  • Le "Matrix Templating" réduit le surcoût mémoire induit par le remplissage (padding) de manière significative (ex: sur MovieLens, le surcoût passe de x100 avec le padding maximal à x2 avec le templating).

5. Signification et Impact

Ce travail comble un vide critique dans le domaine de l'apprentissage automatique préservant la vie privée (PPML). Il démontre que les algorithmes MPC ne sont pas limités aux données denses et peuvent être adaptés aux données réelles de grande dimension.

• Faisabilité : Il rend possible l'exécution sécurisée d'applications ML sur des données massives et creuses qui étaient auparavant inaccessibles en raison de contraintes matérielles.
• Évolutivité : La capacité à supporter un nombre arbitraire de propriétaires de données dans un modèle outsourcé est essentielle pour les écosystèmes de données modernes.
• Équilibre Privé/Efficacité : Les techniques proposées pour minimiser la connaissance publique (sparsité) offrent un compromis pragmatique entre la nécessité d'optimisation algorithmique et la protection de la confidentialité des propriétaires de données.

En résumé, cet article fournit les fondations algorithmiques et pratiques pour déployer des systèmes de ML sécurisés sur des données réelles, massives et creuses, en surmontant les goulots d'étranglement de mémoire et de communication des approches traditionnelles. Le code source est disponible en open-source.