Cryptographie et théorie des jeux pour un découpage équitable de gâteaux

Il était une fois, dans un lointain royaume, un roi très, très vieux. Pour son centième anniversaire, le vieux roi invita tous ses amis les rois et princes des contrées voisines à partager un grand festin suivi d’un énorme gâteau d’anniversaire.

Les monarques se rendirent à la fête et tout se déroula dans la joie et la bonne humeur jusqu’au moment du gâteau d’anniversaire.

Les rois et les princes sont des gens orgueuilleux et capricieux. Lorsque le cuisinier du roi apporta le dessert tant attendu, un énorme gâteau recouvert des 1001 plus délicates douceurs, les souverains commencèrent à se disputer. En effet, chacun des monarques, convaincu de son importance, souhaitait recevoir la plus grande part du gâteau. La tâche de l’intendant du roi, chargé de découper le gâteau, était encore compliquée par les 1001 différents parfums, et par les goûts des souverains qui étaient tous différents. Le pauvre homme se voyait déjà exécuté!

Le ton montait entre les monarques lorsque le mathématicien du roi intervint : « Le découpage de gâteaux, dit-il, est un problème fort étudié en théorie des jeux, qui a de très nombreuses applications pratiques qui vont du partage d’héritage au découpage de parcelles de terrains agricoles. Le problème qui nous intéresse ici est appelé en anglais le « fair cutting » : un découpage tel que chacune des personnes impliquées reçoit au moins autant de gâteau que chacune des autres personnes, en fonction de ses propres goûts et préférences. » Ensuite, le mathématicien parla de l’algorithme « je coupe, tu choisis », de ses généralisations, et de l’algorithme de Su.
« Parfait ! dit le vieux roi. Il suffit donc que chacun des rois donne publiquement ses préférences, qu’on applique l’algorithme de Su, et le problème est réglé ! »

Mais les choses ne furent pas aussi simples. Malins, aucun des rois ne voulait révéler publiquement ses préferences avant les autres. En effet, le dernier roi à révéler ses préférences pourrait mentir en connaissance des préférences des autres monarques, afin de modifier le résultat de l’algorithme en sa faveur.

Ce fut à nouveau le mathématicien qui proposa une solution. « Il suffit, dit-il, que vous choisissiez une personne de confiance, et que chacun d’entre vous lui révèle secrètement ses préférences. Cette personne de confiance sera ce qu’on appelle un médiateur dans la littérature. »

Tous les rois choisirent alors le vieux roi comme médiateur, car il était très apprécié et respecté de ses voisins. Chacun lui révéla ses préférences, l’algorithme de Su fut exécuté, l’intendant ne le fut pas, et la fête continua.


Tout en savourant leurs parts de gâteau respectives (qui étaient d’autant meilleures que chacun, selon ses propres préférences, avait reçu le plus gros morceau), les monarques discutaient des avantages et inconvénients de la solution trouvée.

« Comment ferons-nous pour nous mettre d’accord, dit l’un d’entre eux, lorsque le vieux roi mourra ? Aucun d’entre nous n’est suffisamment digne de confiance pour servir de médiateur.»

Le cryptographe du roi, qui l’air de rien, tendait l’oreille à la conversation dans l’espoir de glâner quelque secret, ne put s’empêcher d’intervenir.

« Les techniques cryptographiques de secure multiparty computation, dit-il, sont de plus en plus utilisables et utilisées en pratique. En principe, elles devraient permettre d’émuler le médiateur de confiance, c’est-à-dire qu’on pourrait exécuter l’algorithme de Su sans médiateur comme si on avait un médiateur, en remplaçant celui-ci par un protocole cryptographique approprié. Je dis bien en principe, car personne n’a encore vraiment testé cette idée. »

« Il faudrait, continua-t-il, sélectionner les protocoles de secure multiparty computation les plus appropriés, implémenter les algorithmes en utilisant des librairies existantes, et finalement tester leur efficacité en fonction de différents paramètres. »

« Si vous le voulez, conclut-il, je peux demander à un étudiant de dernière master ingénieur de faire une étude sur le sujet... »


Pour ce mémoire, il est indispensable d’avoir suivi ou de suivre le cours de cryptographie (MAT2450) ou un équivalent. Le cours de théorie des nombres (MAT2440) est également conseillé. Des bases de programmation sont nécessaires.

Personnes de référence : Christophe Petit et Olivier Pereira