Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Heuristique de Fiat-Shamir
Résumé
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.
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.
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 .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.