Problème du dîner des cryptographes

Illustration.

Trois cryptographes dînent autour d'une table, au restaurant. Le serveur les informe que le dîner a été payé soit par l'un d'entre eux, soit par la NSA. Les cryptographes souhaitent savoir si c'est la NSA qui a payé ou si c'est l'un d'entre eux, mais dans ce dernier cas, sans dévoiler lequel des trois a payé. Ils exécutent donc un protocole en deux étapes.

D'abord, chaque paire de cryptographes choisit un bit secret, partagé entre eux (par exemple, ils laissent une pièce derrière leur menu de façon que seuls les deux cryptographes voient le résultat). Supposons par exemple que les cryptographes A et B partagent le bit ${\displaystyle 1}$, A et C le bit ${\displaystyle 0}$, et B et C le bit ${\displaystyle 1}$.

Ensuite, chaque cryptographe annonce un bit qui est :

• s'il n'a pas payé le repas, le ou exclusif (XOR) des deux bits secrets qu'il connaît avec ses voisins,
• s'il a payé, la négation de ce XOR.

Supposons qu'aucun des cryptographes n'ait payé, alors A annonce ${\displaystyle 1\oplus 0=1}$, B annonce ${\displaystyle 1\oplus 1=0}$, et C annonce ${\displaystyle 0\oplus 1=1}$. Sinon, si par exemple, A a payé, il annonce ${\displaystyle \lnot (1\oplus 0)=0}$.

Les trois annonces publiques combinées donnent la solution à leur question : on calcule le XOR des trois bits annoncés. Si le résultat est 0, alors aucun des cryptographes n'a payé. Sinon, l'un des cryptographes a payé mais son identité reste inconnue.