# 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.
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 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.
En 2019, les travaux de Canetti et d'autres complétés par ceux de Peikert et Shiehian 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 Σ. 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 {\mathcal {X}}\times {\mathcal {W}}$ dans un langage public $L$. Il sera noté ${\mathcal {A}}$ comme étant l'espace d'engagement, ${\mathcal {C}}$ 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 {\mathcal {A}}$.
* Le défi, où le vérifieur répond un élément $c\in {\mathcal {C}}$.
* La réponse, où le prouveur répondra un élément $r\in R$$^,$.

### 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 : ${\mathcal {H}}:{\mathcal {A}}\times {\mathcal {X}}\to {\mathcal {C}}$.
* Le prouveur commence par générer un élément $a\in {\mathcal {A}}$ comme dans le protocole interactif. Ensuite au moment du défi, le prouveur hache $c={\mathcal {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)$$^,$.

### 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.
Il existe des variantes de la construction où la preuve consiste en une transcription complète de l'échange du protocole Sigma, 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 ${\mathcal {X}}$). 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 ${\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, 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 travaille.

## Exemple
### Protocole de Guillou-Quisquater

Un exemple de cette transformation est la signature Fiat-Shamir dérivée du protocole de Guillou-Quisquater. 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}{\bmod {N}}$ 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,\ldots ,N-1\}$, et envoie au vérifieur $Y=y^{e}{\bmod {N}}$. Le vérifieur génère alors un challenge comme un entier $c$ tiré uniformément dans $\{1,\ldots ,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ée.

#### 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:
* GenClefs(λ): On génère $(N,e)$ comme dans le chiffrement RSA, et un couple certificat/secret $(X,x)$ tel que $X=x^{e}{\bmod {N}}$. 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,\ldots ,N-1\}$. Il génère ensuite le challenge $c={\mathcal {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={\mathcal {H}}(Y,m)$ et accepte si et seulement si $Z^{e}=Y\cdot X^{c}$.