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 ( 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 dans un langage public . Il sera noté comme étant l'espace d'engagement, l'espace des challenges, et l'espace des réponses. L'engagement, durant lequel le prouveur envoie au vérifieur un élément . Le défi, où le vérifieur répond un élément . La réponse, où le prouveur répondra un élément .

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 : . Le prouveur commence par générer un élément comme dans le protocole interactif. Ensuite au moment du défi, le prouveur hache et calcule une réponse adéquate pour le défi . Enfin le prouveur envoie comme preuve. Pour vérifier cette preuve, le vérifieur commence par hacher pour obtenir et vérifier que est bien une réponse correcte pour le couple engagement-défi .

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 , 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 est à témoin unique (autrement dit qu'il existe au plus un témoin pour chaque mot de ). Si on envoie , comme l'équation de vérification d'inconnue possède une unique solution , il ne reste alors plus qu'à vérifier que 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 , où 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 , vu comme une clef publique RSA, c'est-à-dire que avec p et q deux grands nombres premiers tirés indépendamment et uniformément parmi les nombres premiers d'une certaine longueur, et est un entier premier avec . Le prouveur qui possède un certificat public veut prouver la connaissance du secret sous-jacent.

Pour cela, lors de l'engagement, le prouveur tire un entier uniformément dans , et envoie au vérifieur . Le vérifieur génère alors un challenge comme un entier tiré uniformément dans . Auquel le prouveur répond en envoyant . Le vérifieur peut alors tester si , 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 comme dans le chiffrement RSA, et un couple certificat/secret tel que . La clef publique est alors et la clef secrète . Signe(sk, m): Pour signer un message , le signataire commence par tirer uniformément dans . Il génère ensuite le challenge et calcule une réponse . La signature est alors . Verifie(pk, m, σ): Pour vérifier la signature , le vérifieur va utiliser Y et m pour calculer et accepte si et seulement si .

Notes et références

Annexes Bibliographie

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

Liens externes

Catégorie:Cryptographie