5 novembre 2026Français
Calcul multipartite (MPC) : le dilemme du millionnaire
1982. Un mathématicien chinois, Andrew Yao, présente dans une conférence d’informatique un court article de cinq pages. La première phrase pose un problème qui ressemble à une blague :
Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth.
Deux millionnaires veulent savoir qui a le plus. Aucun ne veut dire combien il a.
La solution habituelle, c’est un notaire. Les deux lui racontent leur fortune, le notaire compare et annonce le résultat. Ça marche, mais il y a désormais quelqu’un qui connaît les deux chiffres. Ce quelqu’un peut parler, peut être soudoyé, peut se faire voler ses papiers.
Yao propose autre chose : une procédure mathématique pour faire la comparaison sans que personne, pas même un notaire, voie les nombres.
Ainsi naît un domaine qu’on appelle aujourd’hui le calcul multipartite sécurisé, ou MPC. L’idée est celle-ci : plusieurs parties, chacune avec une donnée secrète, calculent quelque chose ensemble. À la fin, chacune connaît le résultat et rien d’autre.

Avec un jeu de cartes
Ça semble impossible, mais ça se fait à une table avec un jeu de cartes. Il faut des trèfles (♣), des cœurs (♥) et deux personnes. Toutes les cartes restent face cachée tout le temps.

Disons que la plus grande fortune possible est 5. Alice en a 3. Bob en a 4.
Alice aligne une rangée de cinq cartes : autant de trèfles que sa fortune, et le reste en cœurs. Sa rangée est ♣♣♣♥♥. Une rampe qui dit « voilà jusqu’où je vais ».

Bob fait à peu près pareil. Il aligne une autre rangée de cinq, tous des trèfles, mais au lieu de compléter avec des cœurs comme Alice, il pose un seul cœur à la position de sa fortune : ♣♣♣♥♣. Un pointeur qui dit « je suis ici ».

Les deux rangées s’entrelacent, une carte d’Alice, une de Bob, toujours face cachée. On ajoute deux cartes de remplissage à la fin.

Ensuite on coupe le jeu. Une fois, dix fois, autant qu’on veut. Chaque coupe change l’endroit où la rangée commence, mais pas l’ordre des cartes entre elles. Maintenant personne ne sait laquelle est la première.

On retourne seulement les cartes de Bob jusqu’à trouver son cœur. On regarde la carte juste à sa gauche. Cette carte est celle d’Alice, et elle est à la même position que la fortune de Bob.

Si c’est un cœur, la rampe d’Alice était déjà terminée : Alice a moins que Bob. Si c’est un trèfle, Alice a autant ou plus.
Ici, c’est un cœur. Alice a moins. Aucun des deux n’a appris le chiffre de l’autre.
Le secret est dans la coupe. Si Bob pouvait choisir où couper, il saurait où commence la rangée et pourrait déduire la fortune d’Alice. Comme la coupe est au hasard, il ne peut pas. Le hasard prend la place du notaire.
Des cartes aux ordinateurs
1986. Yao publie un deuxième article. Les ordinateurs ne mélangent pas de cartes, alors il propose une autre façon de faire la même chose : les circuits brouillés.
Tout calcul peut s’écrire comme un circuit de portes logiques, les plus petites pièces avec lesquelles pense un ordinateur. Une des parties construit le circuit et chiffre chaque porte, de façon qu’elle fonctionne sans montrer ce qui entre ni ce qui sort. L’autre partie le parcourt à l’aveugle, porte par porte, et obtient à la fin le résultat. Rien d’autre.

Quarante ans d’améliorations se sont ajoutées depuis, mais l’idée est la même. Et elle a une condition : ce qu’on veut calculer doit pouvoir s’écrire comme un circuit.

Le prix
Le MPC est lent. Bien plus lent qu’envoyer les données à un serveur et le laisser faire le calcul. Chaque porte chiffrée voyage sur le réseau, et un calcul sérieux en a des millions.
C’est pourquoi on ne l’utilise pas pour tout. On l’utilise quand la donnée ne peut pas sortir, par la loi, par contrat ou par prudence. Là, l’alternative au lent, c’est que ça ne se fasse pas.
Il y a trois façons de calculer avec les données d’autrui :
| Comment on calcule | Vitesse | Qui voit la donnée | Combien de parties |
|---|---|---|---|
| Le cloud ordinaire | élevée | le serveur, tout | une |
| Le chiffrement homomorphe | très faible | personne | un seul propriétaire de la donnée |
| Le MPC | faible | personne | plusieurs, connectées |
Le MPC est le seul des trois où le secret n’est complet nulle part. Et le seul où les parties doivent être connectées et se mettre d’accord à l’avance sur ce qu’elles vont calculer.
Danemark, 2008
Le premier usage réel du MPC n’a pas eu lieu dans une banque ni dans l’armée. Il a eu lieu aux champs.
Janvier 2008. L’Union européenne réforme le marché du sucre, et le Danemark doit redistribuer ses contrats de production de betterave entre ses agriculteurs. La façon juste, c’est une enchère où chacun propose ce qu’il veut sans que les autres voient son offre. Ni l’entreprise sucrière ni l’association des producteurs ne veulent montrer ses chiffres à l’autre, et aucune ne veut d’un intermédiaire qui détiendrait toutes les offres.
Alors l’enchère se fait avec du MPC. Le prix de clôture sort. Aucune offre individuelle n’est jamais vue.

Boston, de vrais salaires
Le deuxième cas, c’est le problème de Yao avec de vrais salaires.
À Boston, un conseil de femmes actives veut mesurer combien les femmes et les personnes non blanches sont payées en moins. Il a besoin des salaires de beaucoup d’entreprises qui se font concurrence pour les mêmes personnes. Aucune ne va remettre sa grille de salaires.
Avec l’université de Boston, le calcul se fait en MPC. En 2016, 69 entreprises y participent avec 112 600 employés. Les salaires ne sont jamais réunis dans une base de données. Un seul chiffre public sort : l’écart.
Ils le répètent six fois entre 2015 et 2023. Dans le dernier, l’échantillon couvre 17 % des salariés de la région.
Le chat et son ombre

« La vraie intimité ne consiste pas à se cacher du monde, mais à collaborer avec lui sans devoir livrer ce qui est à toi. »
Chiffrer, c’est cacher une donnée pour que personne ne la lise. Le MPC fait autre chose : il te permet d’utiliser la donnée avec d’autres sans la livrer.
C’est la même idée qui revient dans toute cette série. PeerDAS vérifie un bloc sans le télécharger. Ğ1 vérifie que quelqu’un est une personne sans registre central. Une adresse furtive encaisse sans que personne ne puisse relier celui qui paie à celui qui reçoit. Toujours la même chose : faire quelque chose avec l’information sans la posséder.
Aujourd’hui, le calcul sur des données qui ne sont pas les tiennes se fait presque toujours comme dans la première scène : on remet la donnée et on fait confiance à l’autre. C’est plus rapide, et ça marche tant que l’autre tient parole.
Yao a trouvé en 1982 une troisième issue, avec deux millionnaires inventés et un jeu de cartes : ne pas avoir à faire confiance à qui que ce soit.