Comprendre le calcul multipartite sécurisé (MPC) - Théorie et pratique
Le calcul multipartite sécurisé (MPC) représente l'une des avancées les plus significatives de la cryptographie, permettant à plusieurs parties de calculer conjointement des fonctions sur des entrées privées sans rien révéler au-delà du résultat. Ce guide complet explore les fondements théoriques, les définitions de sécurité et les applications pratiques du MPC.
Comprendre le calcul multipartite sécurisé
De la théorie à la pratique — Un guide complet des fondements théoriques, des définitions de sécurité et des applications pratiques du MPC
Introduction
Dans les environnements de calcul distribué, plusieurs parties ont souvent besoin de collaborer sur des calculs impliquant des données sensibles. Les approches traditionnelles exigent que les parties fassent confiance à une autorité centrale ou révèlent leurs informations privées. Le calcul multipartite sécurisé résout ce dilemme fondamental en permettant aux parties de calculer des fonctions sur leurs entrées combinées tout en gardant ces entrées privées.
Exigences fondamentales de sécurité
Les protocoles MPC doivent satisfaire plusieurs propriétés critiques :
Confidentialité
Aucune partie n'apprend quoi que ce soit au-delà de sa sortie prescrite. La seule information révélée sur les entrées des autres parties est celle qui peut être déduite de la sortie elle-même.
Exactitude
Chaque partie a la garantie de recevoir la sortie correcte. Aucune partie malveillante ne peut influencer le résultat pour le faire dévier de la fonction spécifiée.
Indépendance des entrées
Les parties corrompues doivent choisir leurs entrées indépendamment de celles des parties honnêtes, ce qui empêche les attaques fondées sur la connaissance des valeurs d'autrui.
Livraison garantie
Les parties corrompues ne devraient pas pouvoir empêcher les parties honnêtes de recevoir leurs sorties au moyen d'attaques par déni de service.
Équité
Les parties corrompues reçoivent des sorties si et seulement si les parties honnêtes reçoivent également les leurs, ce qui empêche le déni sélectif de résultats.
Le paradigme idéal/réel
La définition standard de sécurité pour le MPC suit une approche élégante appelée le paradigme de simulation idéal/réel.
Le monde idéal
Imaginez un monde où une partie de confiance incorruptible existe pour aider aux calculs :
Envoyer les entrées
Calculer la fonction
Renvoyer les sorties
Dans cette exécution idéale, la sécurité est automatique :
| Propriété | Pourquoi elle est vérifiée dans le monde idéal |
|---|---|
| Confidentialité | Les parties ne voient que leurs sorties — rien d'autre n'est révélé |
| Exactitude | La partie de confiance calcule toujours correctement |
| Indépendance des entrées | Les entrées sont envoyées avant qu'aucune sortie ne soit reçue |
| Équité | La partie de confiance délivre toutes les sorties simultanément |
Le monde réel
En réalité, aucune partie de confiance de ce type n'existe. Les parties exécutent plutôt un protocole entre elles, et certaines peuvent être corrompues et complices. Un protocole est considéré comme sécurisé si tout ce qu'un adversaire peut faire lors de l'exécution du protocole réel pourrait également être fait dans l'exécution idéale avec une partie de confiance.
Modèles adverses
La puissance et le comportement des adversaires influencent considérablement la conception des protocoles et les garanties de sécurité.
Comportement adverse
| Modèle | Comportement | Cas d'usage |
|---|---|---|
| Semi-honnête (passif) | Les parties corrompues suivent le protocole mais tentent d'apprendre des informations supplémentaires à partir de leur vue de l'exécution | Modélise une fuite de données involontaire — pas des attaques actives |
| Malveillant (actif) | Les parties corrompues peuvent dévier arbitrairement du protocole | Le modèle de menace le plus fort et le plus réaliste — garantit la sécurité contre toute attaque |
| Furtif (covert) | Les adversaires peuvent se comporter de manière malveillante mais seront détectés avec une probabilité spécifiée | Modélise les scénarios où la détection entraîne des sanctions concrètes — dissuadant les attaques par la responsabilisation |
Stratégies de corruption
| Stratégie | Description | Modélise |
|---|---|---|
| Corruption statique | L'ensemble des parties corrompues est fixé avant le début de l'exécution du protocole | Menaces internes prédéterminées |
| Corruption adaptative | Les adversaires peuvent corrompre des parties pendant l'exécution en fonction de la transcription observée | Pirates externes s'introduisant dans les systèmes ou parties changeant de comportement en cours d'exécution |
| Sécurité proactive | Les parties peuvent devenir corrompues puis se rétablir (redevenir honnêtes) | Violations découvertes et systèmes nettoyés — sécurité garantie contre les adversaires qui ne contrôlent les machines que pendant des périodes limitées |
Résultats fondamentaux de faisabilité
| Seuil | Propriétés | Exigences |
|---|---|---|
| Majorité honnête (t < n/3) | Équité totale et livraison de sortie garantie. Sécurité calculatoire ou théorique de l'information. | Uniquement des canaux authentifiés (et la confidentialité pour le cas théorique de l'information) |
| Majorité honnête (t < n/2) | Équité et livraison garantie. Variantes calculatoire et théorique de l'information. | Canal de diffusion en plus des canaux point à point |
| Pas de majorité honnête (t >= n/2) | Sécurité « avec abandon » — l'adversaire peut apprendre la sortie tout en la refusant aux parties honnêtes. | Limitation inhérente pour certaines fonctions (par ex. le tirage à pile ou face équitable est impossible pour deux parties) |
Techniques fondamentales
Partage de secret de Shamir
Un composant fondamental du MPC à majorité honnête utilisant l'interpolation polynomiale.
Configuration
Reconstruction
Sécurité
Protocole MPC à majorité honnête
En utilisant le partage de secret, les parties peuvent évaluer des circuits arithmétiques de façon sécurisée :
Chaque partie partage ses entrées en utilisant un partage de Shamir (t+1)-parmi-n. Après cette phase, les parties détiennent des parts de toutes les valeurs des fils d'entrée.
Portes d'addition : Chaque partie additionne localement ses parts. Si les parts représentent les polynômes a(x) et b(x), la partie i calcule c(i) = a(i) + b(i). Cela définit c(x) = a(x) + b(x) avec c(0) = a(0) + b(0). Aucune communication n'est nécessaire !
Portes de multiplication : Plus complexes en raison de l'augmentation du degré. La partie i calcule c(i) = a(i) x b(i), ce qui donne un polynôme de degré 2t (et non de degré t). Nécessite une étape de réduction de degré utilisant des partages aléatoires supplémentaires et de la communication pour réduire le degré tout en préservant la valeur en 0.
Les parties envoient les parts des fils de sortie aux destinataires désignés. Les destinataires reconstruisent les sorties par interpolation polynomiale.
Intersection privée d'ensembles (PSI)
La PSI est un problème MPC spécialisé où deux parties disposant des ensembles X et Y veulent calculer X ∩ Y sans révéler les autres éléments.
Génération de clé
PRF oublieuse
Échange
Correspondance
Cryptographie à seuil
La cryptographie à seuil permet des opérations cryptographiques (signature, déchiffrement) sans qu'aucune partie ne détienne la clé privée complète.
Composition modulaire
Une propriété essentielle du MPC sécurisé est la composition modulaire : les protocoles prouvés sécurisés peuvent être utilisés en toute sécurité comme sous-routines dans des systèmes plus vastes.
| Type | Conditions | Garanties |
|---|---|---|
| Composition séquentielle | Les protocoles MPC s'exécutent sans messages concurrents provenant d'autres protocoles | Sécurité préservée dans les systèmes plus vastes. Permet une conception modulaire. Le MPC est traité comme une abstraction de partie de confiance. |
| Composition concurrente (UC) | Plusieurs instances de protocole s'exécutent simultanément | La composabilité universelle (UC) offre les garanties les plus fortes. Les protocoles UC-sécurisés restent sécurisés quelles que soient les exécutions concurrentes. Norme de référence, mais avec un coût en efficacité. |
Considérations pratiques
Avancées en matière d'efficacité
La dernière décennie a vu le MPC passer de curiosité théorique à outil pratique :
Améliorations algorithmiques
Réduction de la surcharge cryptographique de plusieurs ordres de grandeur grâce à une meilleure conception des protocoles
Optimisation matérielle
Exploitation d'AES-NI et d'autres instructions spécialisées pour des opérations cryptographiques plus rapides
Compilateurs personnalisés
Traduction de code de haut niveau en circuits optimisés — minimisant les coûteuses portes AND tout en autorisant les portes XOR peu coûteuses
Optimisation des communications
Réduction des besoins en bande passante et utilisation de techniques de prétraitement pour déplacer le calcul hors ligne
Déploiements en conditions réelles
Étude sur l'écart salarial de Boston
Analyse de 166 705 employés répartis dans 114 entreprises. Calcul de statistiques salariales par genre sans révéler les salaires individuels. Le MPC au service du bien commun.
Conversion publicitaire Google
Calcule l'intersection entre les personnes ayant vu les publicités et les acheteurs effectifs. Protège la confidentialité des utilisateurs tout en permettant des mesures de conversion précises.
Protection des clés cryptographiques
Cryptographie à seuil pour la gestion des clés en entreprise. Protège les clés de signature sans point unique de compromission. Utilisée dans la conservation de cryptomonnaies et la PKI.
Gouvernement estonien
Combinaison des registres fiscaux et éducatifs pour analyser l'impact sur l'emploi des étudiants. Confidentialité et conformité réglementaire préservées.
Apprentissage automatique respectueux de la vie privée
Apprentissage automatique sur données chiffrées. Lutte contre le blanchiment d'argent entre institutions financières. Évaluation des risques sans partage de données.
Mises en garde importantes
Compromis de performance
| Facteur | Impact |
|---|---|
| Latence | Souvent 10 à 1000 fois plus lent que le calcul en clair |
| Bande passante | Les protocoles cryptographiques nécessitent une communication substantielle |
| Mémoire | Certains protocoles requièrent un stockage important pour les valeurs intermédiaires |
L'avenir du MPC
Le MPC illustre le « jeu de longue haleine » de la recherche — de la théorie pure au déploiement pratique en trois décennies.
Progrès récents
Améliorations de performance de plusieurs ordres de grandeur. Implémentations et outils matures. Adoption croissante par l'industrie et efforts de standardisation.
Défis restants
Rendre le MPC accessible aux non-experts. Traiter efficacement de très grands jeux de données. Prendre en charge des calculs complexes de façon économique.
Pistes prometteuses
Approches hybrides combinant le MPC avec d'autres techniques. Accélération matérielle et puces spécialisées. Meilleurs outils de compilation et d'optimisation.
Conclusion
Le calcul multipartite sécurisé est passé d'une possibilité théorique à une réalité pratique. Ses solides garanties de sécurité — formalisées par le paradigme idéal/réel — assurent que les protocoles se comportent comme si une partie de confiance incorruptible effectuait le calcul. Avec les progrès continus en matière d'efficacité et d'utilisabilité, le MPC devient un outil essentiel pour le calcul respectueux de la vie privée dans un monde de plus en plus axé sur les données.
Références
Cet article s'appuie sur « Secure Multiparty Computation » de Yehuda Lindell, initialement publié dans Communications of the ACM, janvier 2021, vol. 64, no 1, pages 86-96.