Heuristique de Fiat-Shamir

L’heuristique de Fiat-Shamir (ou transformation de Fiat-Shamir) est, en cryptographie, une technique permettant de transformer génériquement une preuve à divulgation nulle de connaissance en preuve non-interactive à divulgation nulle de connaissance. Cette preuve peut directement être utilisée pour construire un schéma de signature numérique. Cette méthode a été découverte par Amos Fiat et Adi Shamir en 1986^[1].

Cette heuristique est dénommée ainsi puisque sa première version a été présentée sans preuve de sécurité. David Pointcheval et Jacques Stern ont montré la sécurité de l'heuristique de Fiat-Shamir contre les attaques séquentielles à texte-clair choisi^[2] dans le modèle de l'oracle aléatoire. Par la suite Shafi Goldwasser et Yael Tauman ont montré que sans l'hypothèse sur l'oracle aléatoire, l'heuristique de Fiat-Shamir ne pouvait pas être prouvée sûre sous les hypothèses de sécurité usuelles sur les fonctions de hachage cryptographiques^[3].

En 2019, les travaux de Canetti et d'autres^[4] complétés par ceux de Peikert et Shiehian^[5] ont permis de montrer que l’heuristique de Fiat-Shamir pouvait être instanciée dans le modèle standard à partir d'une famille de fonctions de hachage qui vérifient une propriété supplémentaire : l’impossibilité face aux correlations (correlation intractable en anglais). Ces fonctions de hachage peuvent être obtenues à partir d'un chiffrement complètement homomorphe, et nécessitent donc, à l’heure actuelle, de reposer sur des hypothèses de sécurité sur les réseaux euclidiens.

Transformation de Fiat-Shamir

Pour des raisons de simplicité, la transformation de Fiat-Shamir va être présentée pour le cas des protocoles Σ^[6]. Il s'agit d'un protocole de preuve interactif en trois étapes : l'engagement, le défi et la réponse.

Protocole Σ initial

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

Version non-interactive

À 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].

Intuition

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

Exemple

Protocole de Guillou-Quisquater

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.

Protocole d'identification interactif

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

Signature dérivée par l'heuristique de Fiat-Shamir

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}}$.

Notes et références

1. Fiat et Shamir 1986.
2. Pointcheval et Stern 1996.
3. Goldwasser et Tauman 2003.
4. Canetti et al. 2019.
5. Peikert et Shiehian 2019.
6. Damgård 2010.
7. Damgård 2010, Sec. 2.
8. Kiltz, Masny et Pan 2016, Figure 2.
9. Kiltz et Masny Pan, Sec. 2.4.
10. Miller 2016, Sec. 7.3.
11. Pointcheval et Stern 1996, Sec. 4.1.
12. Baldimtsi et Lysyanskaya 2013, Sec 2.1.
13. Schnorr 1991.
14. Schnorr 1991, Sec. 2. § Protocol for Signature Verification.
15. Guillou et Quisquater 1988.
16. Kiltz, Masny et Pan 2016, Sec. 5.3.2.
17. Kiltz, Masny et Pan 2016, Sec. 5.3.3.

Annexes

Bibliographie

• [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)

Articles connexes

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

Liens externes

• [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

• Portail de la cryptologie