Mise en gage

En cryptologie, la mise en gage (en anglais : commitment scheme) est un processus qui permet à une personne de « mettre en gage » une valeur (ou un énoncé) tout en la maintenant cachée aux autres, avec la possibilité de révéler cette valeur plus tard en prouvant que c'est bien la valeur qui avait été mise en gage^[1]. La mise en gage est conçue de telle sorte que la personne est liée à la valeur mise en gage.

En pratique, la mise en gage se fait en calculant une valeur de mise en gage à partir de la valeur que l'on veut cacher et en communiquant cette valeur de mise en gage à un destinataire. Par la suite, lorsque la valeur originellement cachée sera communiquée au destinataire, celui-ci pourra vérifier que la valeur qui lui a été révélée est bien la valeur qui a servi à calculer la valeur de mise en gage. Plus formellement, la mise en gage transforme une valeur ${\displaystyle m}$ en une paire ${\displaystyle (c,d)}$ de telle façon que 1) ${\displaystyle c}$ ne révèle aucune information sur ${\displaystyle m}$, mais que, 2) ensembles, ${\displaystyle c}$ et ${\displaystyle d}$ permettent de révéler ${\displaystyle m}$, et que 3) il est impossible de trouver ${\displaystyle d'}$ tel que ${\displaystyle (c,d')}$ révèle ${\displaystyle m'\neq m}$.

Les mises en gage ont des applications importantes dans un certain nombre de protocoles cryptographiques, y compris le jeu de pile ou face sécurisé, les preuves à divulgation nulle de connaissance, les signatures numériques et les calculs sécurisés à plusieurs participants.

Le concept de mise en gage a été formalisé par Gilles Brassard, David Chaum et Claude Crépeau en 1988^[2], mais le concept avait été utilisé sans être traité formellement avant cela^[3],[4]. La notion de mise en gage est mentionnée dans les travaux de Manuel Blum^[5], Shimon Even^[6] et Shamir et coll^[7]. Le terme anglais commitment scheme semble avoir été créé par Blum^[4].

Illustration

Une façon de visualiser un système de mise en gage est de penser à un expéditeur qui met un message dans un coffre-fort fermé à clé et qui donne le coffre-fort à un destinataire. Le message dans le coffre-fort est caché au destinataire qui ne peut pas ouvrir la serrure. Étant donné que le destinataire est en possession du coffre-fort, le message à l'intérieur du coffre-fort ne peut pas être changé. Par contre, le message peut être révélé au destinataire si l'expéditeur choisit de lui donner la clé à un moment donné.

Implantation

Les interactions dans un système de mise en gage se déroulent en deux phases :

1. la phase de mise en gage au cours de laquelle une valeur (ou un énoncé) est mise en gage (c'est-à-dire mise dans le coffre-fort fermé à clé de l'exemple précédent) ;
2. la phase de révélation au cours de laquelle la valeur (ou l'énoncé) est révélée et vérifiée.

Dans les protocoles simples, la phase de mise en gage est constituée d'un seul message de l'expéditeur au destinataire. Ce message est appelé la mise en gage (ou l'engagement). Ce message est en fait une valeur que l'expéditeur a calculée à partir du message caché. Il est essentiel que la valeur mise en gage ne puisse pas être calculée par le destinataire à partir de la mise en gage (cette propriété est appelée la dissimulation - en anglais : hiding property). Une phase de révélation simple consisterait en un seul message, la révélation de la valeur originellement cachée, de l'expéditeur au destinataire, suivie d'une vérification effectuée par le récepteur. Il est important que l'expéditeur ne puisse pas calculer une autre valeur qui donnerait la même valeur de mise en gage que sa valeur cachée originale (cette propriété est appelée la liaison - en anglais : binding property).

Applications

Un jeu de pile ou face sécurisé à distance

Supposons qu'Alice et Bob veulent résoudre un certain différend en tirant à pile ou face. S'ils sont physiquement au même endroit, une procédure typique pourrait être :

1. Alice choisit pile ou face et annonce son choix ;
2. Bob lance une pièce de monnaie ;
3. si Alice a prédit le résultat obtenu par Bob, elle gagne, sinon Bob gagne.

Si Alice et Bob ne sont pas au même endroit, un problème se pose. Une fois qu'Alice a fait et annoncé son choix, Bob peut annoncer le résultat qui l'avantage sans qu'Alice puisse vérifier s'il dit vrai. De même, si Alice fait son choix et ne l'annonce pas, après que Bob ait lancé la pièce de monnaie et annoncé le résultat, Alice peut annoncer le résultat qui l'avantage sans que Bob puisse vérifier si elle dit vrai.

Alice et Bob peuvent utiliser la mise en gage pour contourner ce problème :

1. Alice choisit pile ou face, mais communique uniquement la valeur de mise en gage de son choix ;
2. Bob lance la pièce et annonce le résultat ;
3. Alice révèle son choix (à ce point, Alice et Bob connaissent le gagnant probable, mais Bob n'est pas certain qu'Alice a dit vrai) ;
4. Bob vérifie que la valeur de mise en gage de son choix correspond à son choix (à ce point, Bob sait si Alice a dit vrai et le gagnant est connu avec certitude).

Pour que Bob puisse fausser le résultat en sa faveur, il doit être capable de calculer le choix d'Alice à partir de la valeur de mise en gage. Si l'algorithme de mise en gage est de bonne qualité, Bob ne peut faire ce calcul et, conséquemment, il ne peut fausser le résultat en sa faveur. De même, Alice ne peut pas influer sur le résultat, car un algorithme de bonne qualité ne lui permet pas de trouver un autre choix qui aurait la même valeur de mise en gage que celle qu'elle a annoncée^[3],[5].

Preuves à divulgation nulle de connaissance

Signatures numériques

Secrets répartis vérifiables

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Commitment scheme » (voir la liste des auteurs).

1. Oded Goldreich (2001). Foundations of Cryptography: Volume 1, Basic Tools, (draft available from author's site). Cambridge University Press. (ISBN 0-521-79172-3). (voir aussi http://www.wisdom.weizmann.ac.il/~oded/foc-book.html) p. 224
2. Gilles Brassard, David Chaum, et Claude Crepeau, Minimum Disclosure Proofs of Knowledge, Journal of Computer and System Sciences, vol. 37, pp. 156–189, 1988.
3. Moni Naor, Bit Commitment Using Pseudorandomness, Journal of Cryptology 4: 2 pp. 151–158, 1991.
4. Claude Crépeau, Commitment, MCgill.ca, accessed April 11, 2008
5. Manuel Blum, Coin Flipping by Telephone, Proceedings of CRYPTO 1981, pp. 11–15, 1981, reprinted in SIGACT News vol. 15, pp. 23–27, 1983.
6. Shimon Even. Protocol for signing contracts. In Allen Gersho, ed., Advances in Cryptography (proceedings of CRYPTO '82), pp. 148–153, Santa Barbara, CA, USA, 1982.
7. A. Shamir, R. L. Rivest, et L. Adleman, Mental Poker. In D. Klarner, ed., The Mathematical Gardner, pp. 37–43. Wadsworth, Belmont (Californie), 1981.

• Portail de la cryptologie