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.