Protocole d'authentification de Schnorr

• Un nombre ${\displaystyle q}$ premier. On note qu'il définit un groupe ${\displaystyle G}$ d'ordre ${\displaystyle q}$ engendré par ${\displaystyle g}$, noté multiplicativement dans la suite.
• Un élément de groupe ${\displaystyle g}$, d'ordre ${\displaystyle q.}$ C'est ici un générateur d'un sous-groupe d'ordre ${\displaystyle q}$ de ${\displaystyle G}$
• ${\displaystyle q,g}$ sont publics.

• Un entier pris au hasard ${\displaystyle s}$ dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$.
• Le prouveur calcule ${\displaystyle v=g^{s}}$, et ${\displaystyle v}$ est rendu public, certifié par une autorité de confiance, tandis que ${\displaystyle s}$ est gardé secret.

Dans un premier temps, P lance une étape d'engagement:

• P tire au hasard un entier ${\displaystyle r}$ dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$.
• P calcule ${\displaystyle R=g^{r}}$ et envoie ${\displaystyle R}$ à V

Ensuite commence la phase du défi:

• V tire un entier ${\displaystyle c}$ dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$ et l'envoie à P

Finalement, la phase de réponse:

• P calcule ${\displaystyle a=r-c\cdot s}$ et l'envoie à V.

V accepte si et seulement si à l'issue du protocole, la relation ${\displaystyle R=g^{a}\cdot v^{c}}$ est vérifiée.

Pour prouver la sécurité d'un protocole Σ[4], il suffit de prouver la complétude, la robustesse spéciale, et la propriété de non-divulgation de connaissances sous un vérifieur honnête.

La complétude (ou correction) requiert que pour un déroulement honnête du protocole, le vérifieur est toujours convaincu.

Cela se vérifie par la condition d'acceptation de V qui donne que ${\displaystyle g^{a}\cdot v^{c}=g^{r-c\cdot s}\cdot g^{s\cdot c}=g^{r}=R}$, ce qui est toujours vérifié si le protocole s'est déroulé honnêtement.

La robustesse spéciale dit qu'il existe un extracteur de connaissance qui fonctionne en temps polynomial tel qu'étant donné deux transcriptions acceptantes ${\displaystyle (R,c,a)}$ et ${\displaystyle (R,c',a')}$ sous les mêmes paramètres publics, alors l'extracteur renvoie le secret ${\displaystyle s}$.

Cet extracteur se construit comme suit dans le cas du protocole de Schnorr : il va calculer et retourner ${\displaystyle {\frac {a-a'}{c'-c}}}$, car cette valeur correspond au logarithme discret de ${\displaystyle v}$ par ${\displaystyle g}$. En effet, les transcriptions ${\displaystyle (R,c,a)}$ et ${\displaystyle (R,c',a')}$ étant acceptantes, les relations ${\displaystyle R=g^{a}\cdot v^{c}}$ et ${\displaystyle R=g^{a'}\cdot v^{c'}}$ sont vérifiées, donnant ainsi ${\displaystyle g^{\left({\frac {a-a'}{c'-c}}\right)}=v}$ puisque ${\displaystyle c\not =c'}$.

Cette propriété se caractérise par l'existence d'un simulateur probabiliste qui fonctionne en temps polynomial qui, étant donné ${\displaystyle (v,c)}$ où ${\displaystyle c}$ est distribué comme un défis correct, alors le simulateur renvoie une transcription ${\displaystyle (R,c,a)}$ distribuée comme une vraie transcription pour ${\displaystyle v}$. On remarque que le simulateur n'a pas besoin du secret.

Ici, le simulateur va donc générer la réponse avant l'engagement: il va tirer ${\displaystyle a}$ uniformément dans ${\displaystyle \mathbb {Z} _{q}^{\star }}$ et va générer ${\displaystyle R}$ pour qu'il vérifie la condition d'acceptation, c'est-à-dire ${\displaystyle R=g^{a}\cdot v^{c}}$, et va renvoyer ${\displaystyle (R,c,a)}$. On peut remarquer que ${\displaystyle R}$ est distribué uniformément puisque son logarithme discret selon la base ${\displaystyle g}$ l'est. Et par construction ${\displaystyle a}$ est distribué comme une réponse acceptante vis-à-vis de ${\displaystyle (R,c)}$.

La spécification du brevet indique que le groupe ${\displaystyle G}$ doit être choisi comme un sous-groupe d'au moins 140 bits d'un groupe ${\displaystyle \mathbb {Z} _{p}}$ où ${\displaystyle p}$ est un nombre premier de 512 bits pour 72 bits de sécurité.

Une signature numérique est donnée par un triplet d'algorithmes (GenClefs, Signer, Vérifier).

Génération de clefs:

1. Les paramètres publiques (${\displaystyle q}$ et ${\displaystyle g}$) sont générées de la même manière que pour le protocole Σ.
2. Une fonction de hachage ${\displaystyle {\mathcal {H}}:G\times \{0,1\}^{*}\to \mathbb {Z} _{q}^{\star }}$ est ensuite générée et rajoutée aux paramètres publiques.
3. Pour générer une paire de clefs (vk, sk) (v pour vérification, et s pour signature), le signataire commence par tirer uniformément un nombre ${\displaystyle s\in \mathbb {Z} _{q}^{\star }}$, et va le définir comme sa clef secrète.
4. Le signataire va ensuite calculer ${\displaystyle v=g^{s}}$, et va le publier comme sa clef publique.

Signature(sk, m):

1. Pour signer un message, le signataire va commencer par tirer un nombre ${\displaystyle r\in \mathbb {Z} _{q}^{\star }}$ au hasard, et définir ${\displaystyle R=g^{r}}$.
2. Le « défi » va ensuite être généré comme ${\displaystyle c={\mathcal {H}}(R,m)}$, et la réponse calculée comme ${\displaystyle a=r-c\cdot {\mathsf {sk}}\in \mathbb {Z} _{q}}$.
3. Finalement la signature est renvoyée: ${\displaystyle \sigma =(c,a)}$.

Vérification(vk, m, σ):

1. Pour vérifier la signature ${\displaystyle \sigma =(c,a)}$, un utilisateur commence par recalculer ${\displaystyle R}$ en utilisant la clef publique : ${\displaystyle R'=g^{a}\cdot {\mathsf {vk}}^{c}}$.
2. L'utilisateur va ensuite accepter si et seulement si ${\displaystyle {\mathcal {H}}(R',m)~{\overset {?}{=}}~c}$.

Cela donne une signature de taille ${\displaystyle |c|+|a|=280{\mbox{ bits}}=35{\mbox{ octets}}}$ suivant les recommandations minimales du brevet pour 72 bits de sécurité.

Pointcheval et Stern ont montré en 1996 que l'heuristique de Fiat-Shamir[3] est sûre dans le modèle de l'oracle aléatoire[5] si le schéma d'identification sous-jacent est sûr.

• [Feige Fiat et Shamir 1988] (en) Uriel Feige, Amos Fiat et Adi Shamir, « Zero-knowledge proofs of identity », Journal of Cryptology,‎ 1988 (DOI 10.1007/BF02351717)
• [Fiat et Shamir 1986] (en) Amos Fiat et Adi Shamir, « How To Prove Yourself: Practical Solutions to Identification and Signature Problems », Crypto 1986,‎ 1986 (lire en ligne [PDF])
• [Schnorr 1989] (en) Claus-Peter Schnorr, « Efficient Identification and Signature for Smart Cards », Theory and Application of Cryptology, Springer,‎ 1989 (lire en ligne)
• [Pointcheval et Stern 1996] (en) David Pointcheval et Jacques Stern, « Security Proofs for Signature Schemes », Eurocrypt,‎ 1996 (lire en ligne [PDF])

• Cryptographie asymétrique
• Preuve à divulgation nulle de connaissance
• Signature numérique
• Heuristique de Fiat-Shamir

• [Damgård 2010] (en) Ivan Damgård, « On Σ-Protocols », Notes de cours [PDF],‎ 2010