Wiki du cours

Rédacteur: [Julien Python]

A traiter [Modifier]

• Mise en gage, intuition de la boîte fermée à clef.
• Définition ([1] Section 1.2, [2])
• Sécurité: propriété occultante parfaite/conditionnelle, propriété contraignante parfaite/conditionnelle [1, 3].
• Mise en gage en utilisant une fonction de hâchage, fournissant une occultation seulement conditionnelle.
• Mise en gage homomorphe, mise en gage de Pedersen [2, 3], fournissant une occultation parfaite.
• Quelques mots sur les applications ([1] Section 4)

Mise en gage, intuition [Modifier]

De manière informelle, une façon de visualiser un système de mise en gage (commitment scheme en anglais) est de penser à un expéditeur qui met un message (valeur) dans un coffre-fort fermé à clé et qui donne le coffre-fort à un destinataire. Le message (valeur) dans le coffre-fort est caché au destinataire qui ne peut pas ouvrir la serrure. Puisque le destinataire est en possession du coffre-fort, le message (valeur) à l'intérieur du coffre-fort ne peut pas être changé. Par contre, le message (valeur) peut être révélé au destinataire si l'expéditeur choisit de lui donner la clé à un moment donné. \(^{[4]}\)

On souhaite que le message (valeur) ne puisse pas être modifié une fois que le coffre-fort a été fermé.

Définition [Modifier]

Définition : une mise en gage pour un espace de message (valeur) \(M\) est un triplet \((Setup, Commit, Open)\) tel que :

1. \(CK\)<-\(Setup(1^k)\) génère la clé publique de gage (notation \(CK\) pour commitment key)
   
2. Pour tout \(m \in M\), \((c,d)\)<- \(Commit_{CK}(m)\) est la paire de gage pour \(m\).
   \(c=c(m)\) sert de valeur de gage , et \(d=d(m)\) de valeur d’ouverture.
   On note \(Commit_{CK}(m)=Commit(m)\) lorsque le contexte \(CK\) est clair.
   
3. \(Open_{CK}(c,d)\)->\(\tilde{m} \in M \cup \perp\) où \(\perp\) est retourné si \(c\) n’est pour aucun message un gage valide.
   On note \(Open_{CK}(c,d)=Open(c,d)\) lorsque le contexte \(CK\) est clair.
   
4. On veut que l’affirmation suivante soit correcte : pour tout \(m \in M\), \(Open(Commit(m))=m\)

Remarque: Si Bob veut mettre en gage une valeur \(m\) à Alice;

1. l’étape commit :Il génère la paire \((c,d)\)<-\(Commit(m)\), et envoie \(c\) à Alice
2. l’étape reveal: Par la suite, lorsqu’il veut ouvrir le message, il envoie \(d\) à Alice, qui calcule \(\tilde{m}\) <- \(Open(c,d)\). Alice accepte si et seulement si \(\tilde{m} \neq \perp\) (c’est le cas par 4 si tout a été fait correctement).

Sécurité: propriété occultante parfaite/conditionnelle, propriété contraignante parfaite/conditionnelle [Modifier]

Afin d’assurer la sécurité de notre problème, on souhaite avoir les propriétés

1. Hiding (occultante) : \(c\) ne donne pas d’information à Alice sur \(m\). C’est difficile pour un adversaire A de générer deux messages \(m_0, m_1 \in M\) tel que A peut discerner leurs boites fermées \(c_0,c_1\). Ceci revient à dire que \(c(m)\) ne révèle pas d’information à propos de \(m\).
2. Binding (contraignante) : Bob ne peut pas ouvrir \(m\) de deux manières différentes. C’est difficile pour un adversaire A de venir avec un triplet \((c,d,d’)\), ie une collision, tel que \((c,d)\) et \((c,d’)\) sont des gages valides pour \(m\) et \(m’\) (où \(m \neq m’\))

La propriété hiding (respectivement binding) est parfaite si elle est vraie absolument, indépendamment de la puissance de calcul de l'attaquant.

La propriété hiding (respectivement binding) est conditionnelle si un adversaire avec une puissance de calcul illimitée peux la casser.

Mise en gage en utilisant une fonction de hachage, fournissant une occultation seulement conditionnelle. [Modifier]

Si on veut mettre en gage un message en utilisant une fonction de hachage, on donnera l'output de la fonction de hachage au destinataire, et lorsqu'on veut dévoiler le message, on lui donnera le message (et il pourra vérifier à l'aide de la fonction de hachage si les outputs sont similaires).

De plus, un gage \(c\) ne révèle pas d’information sur le message -> ok hiding et parfait (comme on l’a vu dans l’exemple de SHA du sujet 21, grâce notemment à la fonction de compression)

Parmi les propriétés des fonctions de hachage, on a qu’elle doit être résistante aux collisions (ie difficile de trouver \(x\) et \(x’\) différents, tel que \(h(x)=h(x’)\)). Et si on modifie le message, l’output de la fonction de hachage sera différent. -> ok binding mais conditionnel, car avec une puissance de calcul illimité on peut trouver des collisions.

Ainsi, la fonction de hachage semble être idéale pour notre problème, toutefois elle n’est pas un homomorphisme. C’est une propriété souhaitable pour notre mise en gage, qui permet entre autre pour l'encryption de clé secrète, que chacun puisse manipuler des ciphertexts (sujet non développé ici, voir sur internet pour plus de détails).

Mise en gage homomorphe, mise en gage de Pedersen, fournissant une occultation parfaite. [Modifier]

Donc au lieu d’utiliser une fonction de hachage pour la mise en gage, on va utiliser un point sur une courbe elliptique. Soit \(E\) une courbe elliptique, \(G\) son générateur, soit \(C \in E\) notre gage (celui qui sera donné), soit \(H \in E\) où le problème du logarithme discret est difficile à résoudre \(H=qG\), \(r\) une valeur aléatoire (pour le hiding) et \(m\) la valeur mise en gage.

\(\quad \quad C=rH+mG\)

Et maintenant on a un homomorphisme : \(C(r_1,a_1)+C(r_2,a_2)=r_1H+a_1G+r_2H+a_2G=(r_1+r_2)H+(a_1+a_2)G=C(r_1+r_2,a_1+a_2)\)

Pour une mise en gage de Pedersen :

1. Bob (celui qui envoie) choisit un message \(m\)
2. Bob décide d’une valeur aléatoire secrète \(r\)
3. Bob produit de \(m\) et \(r\) un gage \(c\) (comme énoncé ci-dessus par exemple)
4. Bob rend \(C\) publique
5. Par la suite, il révèle \(m\) et \(r\)
6. Alice (celle qui a reçu le message) a maintenant \(C,m,r\) et peut vérifier si \(C(m,r)=c\)

Remarque: Si on considère \(C=rH+aG\), il y a \(r’ \neq r\) tel que \(C’=r’H+a’G\) mais on ne peut trouver \(a’\) seulement si on peut résoudre le problème du logarithme discret. On a donc un binding conditionnel et un hiding parfait.

Quelques mots sur les applications [Modifier]

Exemple: Si Alice et Bob veulent jouer à un jeu à distance;

1. Alice choisit \(P\) ou \(F\) 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.

Problème : comment être sûr qu’aucun des deux joueurs ne mente pour gagner le jeu ? En utilisant la mise en gage :

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
4. Bob vérifie que la valeur de mise en gage de son choix correspond à son choix

Exemple: Le partage de secret vérifiable comme expliqué dans l’exposé 27.

Exemple: La preuve à divulgation nulle (zero-knowledge proof, voir le sujet 29), qui permet à quelqu’un de prouver la validité d’une affirmation sans révéler l’information elle-même ou une information supplémentaire.

Références [Modifier]

[1] Yevgeniy Dodis, Introduction to cryptography, Lecture 14
[2] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, Christophe Petit, Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting, Section 2.2
[3] Adam Gibson, From zero knowledge to bulletproofs, Section 2
[4] Wikipedia