Heuristique de Fiat-Shamir

Un protocole Σ se déroule abstraitement de la manière suivante, pour prouver la connaissance d'un élément ${\displaystyle (x,w)\in {\mathcal {X}}\times {\mathcal {W}}}$ dans un langage public ${\displaystyle L}$. Il sera noté ${\displaystyle {\mathcal {A}}}$ comme étant l'espace d'engagement, ${\displaystyle {\mathcal {C}}}$ l'espace des challenges, et ${\displaystyle R}$ l'espace des réponses.

• L'engagement, durant lequel le prouveur envoie au vérifieur un élément ${\displaystyle a\in {\mathcal {A}}}$.
• Le défi, où le vérifieur répond un élément ${\displaystyle c\in {\mathcal {C}}}$.
• La réponse, où le prouveur répondra un élément ${\displaystyle r\in R}$[7][8].

À partir du protocole Σ ci-dessus, une preuve non interactive est construite de la manière suivante : le prouveur simule la présence du vérifieur par une fonction de hachage cryptographique modélisée comme un oracle aléatoire : ${\displaystyle {\mathcal {H}}:{\mathcal {A}}\times {\mathcal {X}}\to {\mathcal {C}}}$.

• Le prouveur commence par générer un élément ${\displaystyle a\in {\mathcal {A}}}$ comme dans le protocole interactif. Ensuite au moment du défi, le prouveur hache ${\displaystyle c={\mathcal {H}}(a,x)}$ et calcule une réponse ${\displaystyle r}$ adéquate pour le défi ${\displaystyle c}$. Enfin le prouveur envoie ${\displaystyle \pi =(a,r)}$ comme preuve.
• Pour vérifier cette preuve, le vérifieur commence par hacher ${\displaystyle (a,x)}$ pour obtenir ${\displaystyle c}$ et vérifier que ${\displaystyle r}$ est bien une réponse correcte pour le couple engagement-défi ${\displaystyle (a,c)}$[9][10].

Intuitivement, cette transformation fonctionne puisque l'utilisation d'une fonction de hachage garantit dans un premier temps que le prouveur n'a pas pu tricher en modifiant calculant l'engagement a posteriori puisque modifier l'engagement revient à changer le défi (avec grande probabilités). Et comme la fonction de hachage est modélisée comme un oracle aléatoire, alors le défi est distribué uniformément, comme dans la version interactive[1].

Il existe des variantes de la construction où la preuve consiste en une transcription complète de l'échange du protocole Sigma[11], c'est-à-dire ${\displaystyle \pi =(a,c,r)}$, mais cela est un peu redondant, puisque le challenge peut-être retrouvé en hachant le message et l'engagement. De la même manière, étant donné le challenge, et si le langage ${\displaystyle L}$ est à témoin unique (autrement dit qu'il existe au plus un témoin pour chaque mot de ${\displaystyle {\mathcal {X}}}$)[12]. Si on envoie ${\displaystyle \pi =(c,r)}$, comme l'équation de vérification d'inconnue ${\displaystyle a}$ possède une unique solution ${\displaystyle a_{0}}$, il ne reste alors plus qu'à vérifier que ${\displaystyle {\mathcal {H}}(a_{0},x)=c}$ pour être sûr que tout s'est bien passé. C'est le cas par exemple de la signature de Schnorr[13], pour éviter des problèmes de représentation d'éléments de groupes, puisque l'engagement est un élément de groupe, là où le challenge et la réponse sont des éléments de ${\displaystyle \mathbb {Z} _{q}^{\star }}$, où ${\displaystyle q}$ est l'ordre du sous-groupe dans lequel on travaille[14].

Un exemple de cette transformation est la signature Fiat-Shamir dérivée du protocole de Guillou-Quisquater[15]. Cette transformation sera décrite dans cette section.

Le protocole de Guillou-Quisquater peut-être vu comme suit. Le prouveur, sous les paramètres publics ${\displaystyle (N,e)}$, vu comme une clef publique RSA, c'est-à-dire que ${\displaystyle N=p\cdot q}$ avec p et q deux grands nombres premiers tirés indépendamment et uniformément parmi les nombres premiers d'une certaine longueur, et ${\displaystyle 1<e<N}$ est un entier premier avec ${\displaystyle N}$. Le prouveur qui possède un certificat public ${\displaystyle X=x^{e}{\bmod {N}}}$ veut prouver la connaissance du secret ${\displaystyle x}$ sous-jacent.

Pour cela, lors de l'engagement, le prouveur tire un entier ${\displaystyle y}$ uniformément dans ${\displaystyle \{1,\ldots ,N-1\}}$, et envoie au vérifieur ${\displaystyle Y=y^{e}{\bmod {N}}}$. Le vérifieur génère alors un challenge comme un entier ${\displaystyle c}$ tiré uniformément dans ${\displaystyle \{1,\ldots ,N-1\}}$. Auquel le prouveur répond en envoyant ${\displaystyle Z=y\cdot x^{c}}$. Le vérifieur peut alors tester si ${\displaystyle Z^{e}=Y\cdot X^{c}}$, et accepter la preuve si et seulement si l'égalité est vérifiée[16].

L'application de l'heuristique de Fiat-Shamir sur ce protocole donne donc le schéma de signature de Guillou-Quisquater[17]:

• GenClefs(λ): On génère ${\displaystyle (N,e)}$ comme dans le chiffrement RSA, et un couple certificat/secret ${\displaystyle (X,x)}$ tel que ${\displaystyle X=x^{e}{\bmod {N}}}$. La clef publique est alors ${\displaystyle (N,e,X)}$ et la clef secrète ${\displaystyle x}$.
• Signe(sk, m): Pour signer un message ${\displaystyle m}$, le signataire commence par tirer ${\displaystyle y}$ uniformément dans ${\displaystyle \{1,\ldots ,N-1\}}$. Il génère ensuite le challenge ${\displaystyle c={\mathcal {H}}(y^{e},m)}$ et calcule une réponse ${\displaystyle Z=y\cdot x^{c}}$. La signature est alors ${\displaystyle \sigma =(y^{e},Z)}$.
• Verifie(pk, m, σ): Pour vérifier la signature ${\displaystyle \sigma =(Y,Z)}$, le vérifieur va utiliser Y et m pour calculer ${\displaystyle c={\mathcal {H}}(Y,m)}$ et accepte si et seulement si ${\displaystyle Z^{e}=Y\cdot X^{c}}$.

• [Baldimtsi et Lysyanskaya 2013] (en) Foteini Baldimtsi et Anna Lysyanskaya, « On the Security of One-Witness Blind Signature Schemes », Asiacrypt, Springer,‎ 2013 (lire en ligne)
• [Canetti et al. 2019] (en) Ran Canetti, Yilei Chen, Justin Holmgreen, Alex Lombardi, Guy Rothblum, Ron Rothblum et Daniel Wichs, « Fiat Shamir: from practice to theory », STOC,‎ 2019
• [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])
• [Guillou et Quisquater 1988] (en) Louis C. Guillou et Jean-Jacques Quisquater, « A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory », Eurocrypt,‎ 1988 (DOI 10.1007/3-540-45961-8_11)
• [Goldwasser et Tauman 2003] (en) Shafi Goldwasser et Yael Tauman, « On the (In)security of the Fiat-Shamir Paradigm », Foundations on Computer Science (FOCS),‎ 2003 (lire en ligne)
• [Kitz, Masny et Pan 2016] (en) Eike Kiltz, Daniel Masny et Jiaxin Pan, « Optimal Security Proofs for Signatures from Identification Schemes », Crypto,‎ 2016 (lire en ligne)
• [Peikert et Shiehian 2019] (en) Chris Peikert et Sina Shiehian, « Noninteractive Zero Knowledge for NP from (Plain) Learning With Errors », Crypto,‎ 2019 (lire en ligne, consulté le 10 décembre 2019)
• [Pointcheval et Stern 1996] (en) David Pointcheval et Jacques Stern, « Security Proofs for Signature Schemes », Eurocrypt,‎ 1996 (lire en ligne [PDF])
• [Schnorr 1991] (en) Claus Peter Schnorr, « Efficient signature generation by smart cards », Journal of Cryptology,‎ 1991 (DOI 10.1007/BF00196725)

• Preuve sans divulgation de connaissance
• Signature numérique
• Fonction de hachage cryptographique
• Protocole de Schnorr
• Guillou-Quisquater

• [Damgård 2010] (en) Ivan Damgård, « On Σ-Protocols », Notes de cours [PDF],‎ 2010
• [Miller 2016] (en) Andrew Miller, « Zero Knowledge Proofs », Notes de cours [PDF], 2016