This page uses content from Wikipedia and is licensed under CC BY-SA.

Heuristique de Fiat-Shamir — Wikipédia

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

Transformation de Fiat-Shamir

Pour des raisons de simplicité, la transformation de Fiat-Shamir va être présentée pour le cas des protocoles Σ[4]. C'est la un protocole de preuve interactif en trois étapes : l'engagement, de 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éfis, où le vérifieur répond un élément .
  • La réponse, où le prouveur répondra un élément [5][6].

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éfis, 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éfis [7][8].

Intuition

Intuitivement, cette transformation fonctionne car l'utilisation d'une fonction de hachage garantie 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éfis (avec grande probabilités). Et comme la fonction de hachage est modélisée comme un oracle aléatoire, alors le défis est distribué uniformément, comme dans la version non-interactive[1].

Il existe des variantes de la construction où la preuve consiste en une transcription complète de l'échange du protocole Sigma[9], 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 )[10]. 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[11], 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[12].

Exemple

Protocole de Guillou-Quisquater

Un exemple de cette transformation est la signature Fiat-Shamir dérivée du protocole de Guillou-Quisquater[13]. 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 publiques , 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 publique 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[14].

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[15]:

  • 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

  • [Baldimtsi et Lysyanskaya 2013] (en) Foteini Baldimtsi et Anna Lysyanskaya, « On the Security of One-Witness Blind Signature Schemes », Asiacrypt, Springer,‎ (lire en ligne)
  • [Fiat et Shamir 1986] (en) Amos Fiat et Adi Shamir, « How To Prove Yourself: Practical Solutions to Identification and Signature Problems », Crypto 1986,‎ (lire en ligne [PDF])
  • [Guillou et Quisquater 1988] Louis C. Guillou et Jean-Jacques Quisquater, « A Practical Zero-Knowledge Protocol Fitted to Security Microprocessor Minimizing Both Transmission and Memory », Eurocrypt,‎ (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),‎ (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,‎ (lire en ligne)
  • [Pointcheval et Stern 1996] (en) David Pointcheval et Jacques Stern, « Security Proofs for Signature Schemes », Eurocrypt,‎ (lire en ligne [PDF])
  • [Schnorr 1991] (en) Claus Peter Schnorr, « Efficient signature generation by smart cards », Journal of Cryptology,‎ (DOI 10.1007/BF00196725)

Articles connexes

Liens externes