Ouvrir le menu principal

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

Sommaire

Transformation de Fiat-ShamirModifier

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 Σ initialModifier

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-interactiveModifier

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

IntuitionModifier

Intuitivement, cette transformation fonctionne car 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é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].

ExempleModifier

Protocole de Guillou-QuisquaterModifier

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 interactifModifier

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-ShamirModifier

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érencesModifier

AnnexesModifier

BibliographieModifier

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

Liens externesModifier