Calcul multipartite sécurisé

Le calcul multipartite sécurisé (MPC) permet à des parties mutuellement méfiantes de calculer conjointement une fonction à partir de leurs entrées privées, sans révéler autre chose que le résultat convenu.

Definition

Le calcul multipartite sécurisé est un protocole permettant à un ensemble de parties, chacune détenant une entrée privée, de calculer une fonction convenue de telle sorte que chaque partie apprenne le résultat correct et rien d'autre concernant les entrées des autres.

Scope

Ce sujet couvre les protocoles de calcul sécurisé : la définition de sécurité par simulation idéale/réelle, les circuits brouillés de Yao pour deux parties, les protocoles basés sur le partage de secrets (GMW, BGW) pour plusieurs parties, la distinction entre sécurité semi-honnête et malveillante, et la cryptographie à seuil. Il aborde des applications pratiques telles que l'intersection d'ensembles privés et l'agrégation sécurisée. Il exclut les preuves à divulgation nulle de connaissance souvent utilisées comme sous-protocole et le chiffrement entièrement homomorphe qui offre une voie alternative pour le calcul sur des données chiffrées.

Core questions

• Comment les parties peuvent-elles calculer sur des données combinées sans qu'aucune partie ne voie les entrées des autres ?
• Qu'exige le paradigme de simulation idéale/réelle d'un protocole sécurisé ?
• Comment les circuits brouillés permettent-ils le calcul sécurisé à deux parties ?
• Comment les protocoles basés sur le partage de secrets s'adaptent-ils à de nombreuses parties et tolèrent-ils les corruptions ?
• Quelle est la différence entre les garanties de sécurité semi-honnête et malveillante ?

Key concepts

• entrées privées et sortie conjointe
• simulation idéale/réelle
• circuits brouillés
• transfert inconscient
• partage de secrets
• adversaire semi-honnête vs malveillant
• cryptographie à seuil
• intersection d'ensembles privés
• majorité honnête vs majorité malhonnête

Key theories

Sécurité par simulation idéale/réelle

Un protocole MPC est sécurisé si tout ce qu'un adversaire peut réaliser dans le protocole réel, il pourrait également l'atteindre dans un monde idéal où une partie de confiance calcule la fonction — garantissant la confidentialité et l'exactitude contre les corruptions modélisées.

Circuits brouillés et partage de secrets

Les circuits brouillés de Yao permettent à deux parties d'évaluer n'importe quel circuit booléen, l'une chiffrant les tables de vérité et l'autre déchiffrant de manière inconsciente ; les schémas de partage de secrets divisent les entrées entre les parties afin que des sous-ensembles calculent conjointement les portes sans reconstruire les secrets.

Mechanisms

Dans le protocole à deux parties de Yao, une partie brouille un circuit booléen en chiffrant la table de vérité de chaque porte, et l'autre l'évalue en utilisant des clés obtenues via un transfert inconscient, n'apprenant que le résultat. Dans les approches de partage de secrets (GMW, BGW, SPDZ), chaque entrée est divisée en parts distribuées entre les parties ; les portes d'addition sont calculées localement sur les parts et les portes de multiplication utilisent une interaction, après quoi les parts de sortie sont reconstruites. La sécurité malveillante ajoute des preuves à divulgation nulle de connaissance ou des parts authentifiées pour détecter la tricherie.

Clinical relevance

Le MPC passe de la théorie au déploiement pour la collaboration respectueuse de la vie privée : les institutions calculent des statistiques agrégées sur des ensembles de données combinés sans regrouper les données brutes (l'étude de Boston sur l'écart salarial entre les sexes), les entreprises effectuent des intersections d'ensembles privés pour la découverte de contacts et la mesure publicitaire, les signatures à seuil protègent la garde de cryptomonnaies et les clés d'autorités de certification, et l'agrégation sécurisée soutient l'apprentissage automatique respectueux de la vie privée.

Evidence & guidelines

Le MPC est soutenu par des frameworks ouverts matures (par exemple, MP-SPDZ) et de plus en plus par des efforts de normalisation en cryptographie à seuil (le projet de cryptographie à seuil multipartite du NIST). Les garanties de sécurité dépendent de manière critique du modèle de corruption supposé (semi-honnête vs malveillant) et du seuil de corruption (majorité honnête vs majorité malhonnête), qui doivent correspondre aux hypothèses de confiance du déploiement.

History

Andrew Yao a introduit le calcul sécurisé à deux parties et l'idée des circuits brouillés entre 1982 et 1986 (le problème des millionnaires). Goldreich, Micali et Wigderson (1987) ont étendu le calcul sécurisé à un nombre quelconque de parties, et les protocoles BGW et CCD (1988) ont fourni une sécurité basée sur la théorie de l'information avec une majorité honnête. Des décennies d'améliorations de l'efficacité (extension du transfert inconscient, SPDZ) ont rendu le MPC suffisamment pratique pour des déploiements réels dans les années 2010.

Key figures

• Andrew Yao
• Oded Goldreich
• Silvio Micali
• Avi Wigderson
• Adi Shamir

Seminal works

• yao1982
• goldreich2004
• katz2020

Frequently asked questions

En quoi le MPC diffère-t-il du chiffrement homomorphe ?

Les deux calculent sur des données privées, mais le chiffrement homomorphe permet à une seule partie de calculer sur des textes chiffrés qu'elle ne peut pas lire, tandis que le MPC distribue le calcul entre plusieurs parties qui interagissent, sans qu'aucune partie ne puisse voir les entrées. Ils sont parfois combinés.

Que signifie la sécurité « semi-honnête » par rapport à « malveillante » ?

La sécurité semi-honnête (honnête mais curieuse) suppose que les parties suivent le protocole mais essaient d'obtenir des informations supplémentaires à partir de ce qu'elles observent. La sécurité malveillante protège en outre contre les parties qui s'écartent arbitrairement du protocole, ce qui est plus robuste mais plus coûteux.