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. La mise en gage est conçue de telle sorte que la personne est liée à la valeur mise en gage.

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.

Concept, historique et terminologie

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

Description

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 $m$ en une paire $(c,d)$ de telle façon que 1) $c$ ne révèle aucune information sur $m$, mais que, 2) ensembles, $c$ et $d$ permettent de révéler $m$, et que 3) il est impossible de trouver $d'$ tel que $(c,d')$ révèle $m'\neq m$.

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.

Preuves à divulgation nulle de connaissance

Une preuve à divulgation nulle de connaissance (Zero Knowledge Interactive proof ou ZKIP en anglais, parfois simplement ZKP) est un protocole cryptographique permettant l'authentification sécurisée d'informations. Dans le cadre de ce protocole, une entité, nommée « fournisseur de preuve » ou prouveur peut démontrer à une autre partie, appelée le vérificateur, qu'une déclaration est vraie, sans révéler aucune information supplémentaire à son sujet. Ces preuves jouent un rôle essentiel dans la garantie de la confidentialité et de la sécurité de divers systèmes cryptographiques modernes.

En pratique, ces schémas se présentent souvent sous la forme de protocoles de type « défi/réponse » (challenge-response). Le vérificateur et le fournisseur de preuve s'échangent des informations et le vérificateur contrôle si la réponse finale est positive ou négative. Il existe également des variantes sans interaction (non-interactive zero-knowledge proof) qui peuvent être construites dans le modèle de l'oracle aléatoire par l'heuristique de Fiat-Shamir.

Les preuves à divulgation nulle reposent sur trois propriétés fondamentales :

• Complétude : si la déclaration est vraie et que le prouveur suit le protocole, le vérificateur sera convaincu.
• Robustesse : si la déclaration est fausse, un prouveur malveillant ne pourra pas convaincre un vérificateur honnête.
• Zéro-connaissance : le vérificateur n'acquiert aucune information supplémentaire sur la déclaration, au-delà de sa véracité.

Les ZKP peuvent être utilisées pour cacher des informations dans un registre distribué (comme une blockchain), tout en permettant la validation de ces informations. Cela est particulièrement utile dans des systèmes où les parties n'ont pas totalement confiance les unes envers les autres, tout en évitant la nécessité d'une tierce partie de confiance.

Signatures numériques

La signature numérique ou signature électronique est un mécanisme permettant d'authentifier l'auteur d'un document électronique et d'en garantir la non-répudiation, par analogie avec la signature manuscrite d'un document papier.

Elle se différencie de la signature écrite par le fait qu'elle n'est pas visuelle, mais correspond à une suite de caractères. Elle ne doit pas être confondue avec la signature électronique manuscrite.

Secrets répartis vérifiables

Le secret réparti ou le partage de secret consiste à distribuer un secret, par exemple une clé ou un mot de passe, entre plusieurs dépositaires. Le secret ne peut être découvert que si un nombre suffisant de dépositaires mettent en commun les informations qu'ils ont reçues. En revanche, un nombre inférieur de dépositaire n’apporte aucune information sur le secret.

Le secret réparti a été inventé indépendamment par Adi Shamir et George Blakley en 1979.

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