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 1986Modèle:Sfn.

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 choisiModèle:Sfn 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 cryptographiquesModèle:Sfn.

En 2019, les travaux de Canetti et d'autresModèle:Sfn complétés par ceux de Peikert et ShiehianModèle:Sfn 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 (Modèle:Langue 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 ΣModèle:Sfn. 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 $(x,w)\in 𝒳\times 𝒲$ dans un langage public $L$. Il sera noté $𝒜$ comme étant l'espace d'engagement, $𝒞$ l'espace des challenges, et $R$ l'espace des réponses.

• L'engagement, durant lequel le prouveur envoie au vérifieur un élément $a\in 𝒜$.
• Le défi, où le vérifieur répond un élément $c\in 𝒞$.
• La réponse, où le prouveur répondra un élément $r\in R$Modèle:SfnModèle:,Modèle:Sfn.

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 : $\mathscr{H}:𝒜\times 𝒳\to 𝒞$.

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

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 interactiveModèle:Sfn.

Il existe des variantes de la construction où la preuve consiste en une transcription complète de l'échange du protocole SigmaModèle:Sfn, c'est-à-dire $\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 $L$ est à témoin unique (autrement dit qu'il existe au plus un témoin pour chaque mot de $𝒳$)Modèle:Sfn. Si on envoie $\pi =(c,r)$, comme l'équation de vérification d'inconnue $a$ possède une unique solution $a_0$, il ne reste alors plus qu'à vérifier que $\mathscr{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 SchnorrModèle:Sfn, 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 ${\mathbb{Z}}_q^{\star }$, où $q$ est l'ordre du sous-groupe dans lequel on travailleModèle:Sfn.

Exemple

Protocole de Guillou-Quisquater

Un exemple de cette transformation est la signature Fiat-Shamir dérivée du protocole de Guillou-QuisquaterModèle:Sfn. 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 $(N,e)$, vu comme une clef publique RSA, c'est-à-dire que $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 $1<e<N$ est un entier premier avec $N$. Le prouveur qui possède un certificat public $X=x^{e}modN$ veut prouver la connaissance du secret $x$ sous-jacent.

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

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-QuisquaterModèle:Sfn:

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

Annexes

Bibliographie

• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article

Articles connexes

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

Liens externes

• Modèle:Lien web
• Modèle:Lien web