Wiki du cours

Rédacteur: Lucia Camenisch

A traiter [Modifier]

• Concept ([1] Section 2)
• Protocole de Schnorr ([1] Section 3.2)
• Idée de Fiat-Shamir transformant le protocole interactif en un protocole non-interactif ([1] Section 3.3)
• Quelques mots sur les applications ([1] Section 5)

Concept [Modifier]

Prenons deux personnes, Pierre et Virginie. Pierre connaît une information secrète et voudrait prouver à Virginie qu'il possède cette information, mais sans rien révéler de l'information elle-même car elle doit rester secrète. Ils vont pour cela mettre au point un procédé ensemble, appelé protocole en cryptographie. Ce type de protocole est une preuve à divulgation nulle de connaissance.

Pierre est généralement appelé le fournisseur de preuve, ou prover en Anglais; et Virginie est appelée la vérificatrice, verifier en Anglais.

Une preuve à divulgation nulle de connaissance doit satisfaire trois critères.

• Elle est cohérente: Si Virginie et Pierre sont tous les deux honnêtes, le protocole doit réussir avec une probabilité très proche de 1.
• Elle est robuste: Si Pierre est malhonnête, la probabilité qu'il réussisse le protocole est négligeable.
• Elle n'a aucun apport d'information: Virginie apprend uniquement si Pierre ment ou non. Elle n'acquiert aucune autre information sur le sujet.

Ces protocoles sont dits interactifs si Virginie et Pierre s'envoie plusieurs messages successifs afin d'exécuter le protocole. Ils sont dits non-interactifs si le protocole consiste uniquement d'un message que Pierre envoie à Virginie.

Exemple [Modifier]

Considérons deux billes, une rouge et une bleue. Elles sont strictement identiques mis à part leurs couleurs. Supposons que Virginie est aveugle. Pierre souhaite prouver à Virginie qu'il peut distinguer les deux billes, mais sans révéler à Virginie les couleurs des billes.

Voici un protocole possible:

1. Virginie prend les deux billes et les tient derrière son dos.
2. Elle montre une des deux billes à Pierre.
3.  Elle remet les billes derrière son dos et les mélange, en faisant bien attention à toujours savoir où se situe celle qu'elle a montré à Pierre.
4.  Elle choisit l'un des deux billes aléatoirement et la montre à Pierre.
5.  Pierre doit dire si c'est la même bille qu'avant ou non.

On va répéter ce protocole un grand nombre de fois. Si Pierre ne distingue pas les couleurs, il a une probabilité de \( \frac{1}{2}\) de répondre correctement à la question de Virginie. Après \(n\) répétitions, Pierre a probabilité \( \left(\frac{1}{2}\right)^n\) de réussir à donner toutes les réponses correctes. Cette probabilité devient bien négligeable pour \(n\) grand.

Protocole de Schnorr [Modifier]

Nous allons maintenant voir un protocole de preuve à divulgation nulle de connaissances utilisé en cryptographie des courbes elliptiques.

Pierre et Virginie choisissent une courbe elliptique sur un corps, \(E(\mathbb{F}_p)\), avec \(p\) premier. Ils choisissent une racine primitive \(G\) de \(E(\mathbb{F}_p)\) ainsi qu'un point \(B\in E(\mathbb{F}_p)\).

Pierre veut prouver à Virginie qu'il a résolu le problème du logarithme discret: il connaît \(x \in \mathbb{N}\) tel que \(B=x \cdot G\). Cependant, souhaite garder ce \(x\) secret! Il faut donc une preuve à divulgation nulle de connaissances. Le protocole de Schnorr est une option possible:

1. Pierre choisit aléatoirement un nombre \(r \in \mathbb{F}_p\) et calcule le point \(A=r \cdot G\).
2. Pierre envoie \(A\) à Virginie.
3. Virginie choisit une fonction de hachage \(HASH\) et calcule \(c=HASH(G,B,A)\), où \(c\) est un entier.
4. Virginie envoie \(c\) à Pierre.
5. Pierre calcule \(m = r + c \cdot x \mod p\).
6. Pierre envoie \(m\) à Virginie.
7. Virginie vérifie que \(m \cdot G - c \cdot B = A\).

La vérification fonctionne bien car: \(m \cdot G - c \cdot B = (r + c \cdot x)\cdot G - c \cdot B = r \cdot G +c \cdot x \cdot G - c \cdot B = A + c \cdot B - c \cdot B= A\)

Dans cet exemple, Virginie n'a pas nécessairement besoin de la fonction de hachage, elle pourrait choisir un \(c\) aléatoirement. La fonction de hachage deviendra nécessaire dans le protocole suivant.

Le protocole de Schnorr, contrairement aux exemples vu ci-dessus, a besoin d'être exécuté une seule fois. Il est très improbable que Pierre trouve la bonne réponse s'il ne connaît pas \(x\).

Idée de Fiat-Shamir [Modifier]

Le protocole de Schnorr est une preuve interactive. Dans leur article, Fiat-Shamir proposent une version non-interactive du protocole.

Comme avant, Virginie et Pierre vont choisir \(E(\mathbb{F}_p)\), \(G\) et \(B\). Ils choisissent également un point \(P \in E(\mathbb{F}_p)\) et une fonction de hachage \(HASH\). Pierre veut toujours prouver qu'il connaît \(x \in \mathbb{N}\) tel que \(B=x \cdot G\), sans révéler \(x\).

Le protocole se déroule ainsi:

1. Pierre choisit aléatoirement un nombre \(r \in \mathbb{F}_p\) et calcule le point \(A=r \cdot G\).
2. Pierre calcule \(c= HASH(xP,rP,A)\).
3. Pierre calcule \(s = r + c \cdot x \mod p\).
4. Pierre envoie à Virginie \((s, xP, rP, A)\).
5. Virginie calcule \(c= HASH(xP,rP,A)\).
6. Virginie vérifie que \( sG= A + cB\).
7. Virginie vérifie que \( sP= rP + c \cdot xP\).

Les vérifications fonctionnent bien: \( sG= (r + c \cdot x)G = rG+ c \cdot xG= A + cB\) \( sP= (r + c \cdot x)P = rP + c \cdot xP\)

Grâce à la valeur de \(c\) donnée par la fonction de hachage, il est comme auparavant impossible pour Pierre de tricher.

Applications [Modifier]

Il existe des applications très diverses des preuves à divulgation nulle de connaissances. Globalement, l'utilisation de protocoles en cryptographie des courbes elliptiques est pratique pour des petits appareils qui n'ont pas beaucoup de puissance, car la taille des clés utilisées est plus petite qu'en cryptographie classique.

Par exemple, lors d'un cours à l'université, le professeur pourrait donner une questionnaire anonyme sur la qualité du cours à la fin de la leçon. Les étudiants pourraient y répondre depuis des petits appareils qu'ils auraient avec eux. Il faudrait que l'appareil de chaque étudiant prouve que l'étudiant en question est bien inscrit et n'est pas un intrus, mais sans révéler les informations personnelles de l'étudiant afin de protéger son anonymat. Il y a donc besoin d'une preuve à divulgation nulle de connaissances.

Références [Modifier]

[1] Ioannis Chatzigiannakis, Apostolos Pyrgelis, Paul G. Spirakis, Yannis C. Stamatiou, Elliptic curve based zero knowledge proofs and their applicability on ressource constrained devices
[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.3
[3] Adam Gibson, From zero knowledge to bulletproofs, Section 3