Le problème du millionnaire (Yao, 1982)

Imaginez deux millionnaires qui se rencontrent à un dîner. Chacun est curieux : lequel des deux est le plus riche ? Mais aucun ne veut révéler le montant exact de sa fortune. Ce petit casse-tête, posé par Andrew Yao en 1982, a fondé tout un domaine de la cryptographie.

Le problème du millionnaire

Alice possède une fortune a, Bob une fortune b. Ils veulent connaître le résultat de la comparaison — savoir si a > b, a < b ou a = b — sans qu'Alice apprenne b, ni que Bob apprenne a.

La solution naïve consisterait à confier les deux chiffres à un tiers de confiance qui ferait la comparaison et annoncerait le gagnant. Mais un tel arbitre n'existe pas toujours : il faudrait lui faire une confiance totale, et il connaîtrait alors les deux fortunes. Yao a montré qu'on peut se passer de cet arbitre.

Du cas particulier au cas général

Le problème du millionnaire n'est qu'un exemple. Sa généralisation s'appelle le calcul multipartite sécurisé (en anglais secure multi-party computation, souvent abrégé MPC).

Plusieurs parties, disons P1, P2, ..., Pn, détiennent chacune une entrée privée x1, x2, ..., xn. Elles veulent calculer ensemble une fonction commune :

resultat = f(x1, x2, ..., xn)

La garantie recherchée est double :

• Correction : le résultat calculé est bien f(x1, ..., xn), la vraie valeur.
• Confidentialité : chaque partie n'apprend que le résultat, et rien de plus sur les entrées des autres que ce que le résultat lui-même révèle.

L'idée centrale en une image

   x1 (privé)  x2 (privé)  x3 (privé)
      \           |           /
       \          |          /
        +---------+---------+
        |  protocole MPC    |   <- personne ne voit x1, x2, x3
        +---------+---------+
                  |
                  v
             f(x1,x2,x3)          <- seul le résultat sort

Les entrées entrent d'un côté, chiffrées ou découpées ; seul le résultat ressort. Aucune partie, ni aucun observateur, n'accède aux entrées individuelles.

À quoi cela sert-il ?

Les applications sont nombreuses dès que des acteurs veulent coopérer sans se faire confiance :

• Enchères scellées : déterminer le plus offrant sans dévoiler les offres perdantes.
• Statistiques de salaires : calculer le salaire moyen d'un groupe sans qu'aucun employé ne révèle le sien.
• Analyses médicales inter-hôpitaux : croiser des données de patients entre établissements pour la recherche, sans partager les dossiers individuels.

Dans chaque cas, la valeur agrégée est utile à tous, mais les données brutes doivent rester privées. Le MPC rend exactement cela possible.

En résumé

Le MPC permet à plusieurs parties de calculer une fonction de leurs entrées privées de sorte que chacune n'apprenne que le résultat, jamais les entrées des autres. Le problème du millionnaire de Yao (1982) en est l'exemple fondateur ; enchères, statistiques et analyses médicales en sont des usages concrets.