De l'interactif à la signature

La transformation de Fiat-Shamir

Le protocole de Schnorr a un défaut pratique : il exige un vérifieur en ligne pour envoyer le défi c. Impossible, dans ces conditions, de signer un document que quelqu'un lira demain. La transformation de Fiat-Shamir (1986) supprime cette contrainte d'un coup de génie.

L'idée : remplacer le hasard par un haché

D'où vient le défi c ? Du vérifieur, qui le tire au hasard. Sa seule vertu est d'être imprévisible pour le prouveur au moment où il choisit t. Fiat et Shamir font l'observation suivante : une fonction de hachage est, elle aussi, imprévisible. Alors, remplaçons le vérifieur par un calcul :

c = H(t)          (ou, pour signer un message m : c = H(t, m))

Le prouveur calcule lui-même son défi en hachant son propre engagement. Comme H est imprévisible, il ne peut pas choisir t en fonction de c (il faudrait connaître c avant de calculer t, alors que c dépend de t). Le piège de la soundness reste donc fermé.

Interactif contre non interactif

   AVANT (interactif)              APRÈS (Fiat-Shamir, non interactif)
   -----------------              -----------------------------------
   P --- t --------> V            P calcule t = g^r
   P <-- c (aléa) -- V            P calcule c = H(t, m)   <- plus de V !
   P --- s --------> V            P calcule s = r + c*x
        V vérifie                 P publie (t, s) ou (c, s)
                                  n'importe qui vérifie avec y

Le bénéfice est immense : plus besoin de vérifieur en ligne. Le prouveur produit à lui seul un triplet auto-suffisant. N'importe qui, plus tard, recalcule c = H(t, m) à partir des éléments publics et vérifie g^s = t * y^c. La preuve interactive est devenue une preuve autonome, transmissible et vérifiable par tous.

Une recette générale

Fiat-Shamir n'est pas un tour de passe-passe propre à Schnorr : c'est une recette générale. Tout protocole du type engagement – défi – réponse peut être rendu non interactif en remplaçant le défi aléatoire par le haché de l'engagement. C'est l'un des outils les plus universels de la cryptographie moderne, au cœur d'innombrables signatures et systèmes de preuve (jusqu'aux zk-SNARKs).

Le prix à payer

Cette magie a deux conditions :

Un bon aléa. Le nonce r reste indispensable et doit toujours être frais et secret. La transformation ne dispense pas de la discipline vue au chapitre précédent — au contraire, un r réutilisé reste catastrophique.
Le modèle de l'oracle aléatoire. La preuve de sécurité suppose que H se comporte comme une fonction parfaitement aléatoire (un oracle aléatoire). C'est une idéalisation : aucune fonction réelle ne l'est tout à fait. En pratique, avec une bonne fonction comme SHA-256, la construction résiste, mais la garantie théorique repose sur ce modèle idéalisé.

En résumé