← Retour au journal

Calcul multipartite (MPC) : le dilemme du millionnaire

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.

Slide : deux chats ninja avec des sacs d'argent, et la pensée de l'un : a-t-il plus que moi ?

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.

Slide : le chat ninja mélange un jeu sur une table en bois

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 ».

Slide : le chat ninja aligne trois trèfles et deux cœurs sur cinq cartes face cachée

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 ».

Slide : la rangée de Bob avec un seul cœur en quatrième position

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.

Slide : le chat ninja entrelace les deux rangées et marque deux fausses cartes à 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.

Slide : le chat ninja coupe le jeu en l'air avec son sabre

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.

Slide : le chat ninja à la loupe regarde la carte à gauche du cœur 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.

Slide : le chat ninja devant une machine de tuyaux et de coffres-forts avec des portes AND et XOR

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.

Slide : le tableau comparatif entre le tour de cartes et la version cryptographique

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 calculeVitesseQui voit la donnéeCombien de parties
Le cloud ordinaireélevéele serveur, toutune
Le chiffrement homomorphetrès faiblepersonneun seul propriétaire de la donnée
Le MPCfaiblepersonneplusieurs, 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.

Slide : le chat ninja en détective dans un marché de légumes, avec une betterave géante sur le côté

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

Slide : le chat ninja et sa propre ombre, avec un as de cœur sur la table

« 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.