De l'interactif à la signature

Les signatures de Schnorr et leur renaissance

Appliquons la recette de Fiat-Shamir au protocole d'identification de Schnorr. Le résultat porte un nom : les signatures de Schnorr. Longtemps restées dans l'ombre, elles connaissent aujourd'hui une éclatante renaissance.

De l'identification à la signature

La transformation est directe. Pour signer un message m avec sa clé privée x :

1. tirer un aléa r,  calculer t = g^r
2. calculer c = H(t, m)
3. calculer s = r + c*x
   -> la signature est le couple (t, s)   [ou (c, s)]

Pour vérifier, avec la clé publique y = g^x :

recalculer c = H(t, m)
accepter si g^s = t * y^c

C'est exactement l'identification de Schnorr, où le défi n'est plus tiré par un vérifieur mais calculé par hachage. La signature lie le message m à la clé, et personne ne peut la forger sans connaître x.

Trois qualités remarquables

Les signatures de Schnorr se distinguent par trois vertus :

Simplicité. La construction est minimale : une exponentiation, un hachage, une addition. Peu de pièces, donc peu de choses à casser.
Sécurité prouvable. On sait démontrer leur sûreté (dans le modèle de l'oracle aléatoire), ce qui n'est pas le cas de tous les schémas concurrents.
Linéarité. C'est la propriété la plus précieuse. La réponse s = r + c*x est linéaire en x et en r. Deux signatures peuvent donc s'additionner : les s s'ajoutent, les engagements se combinent. Cela ouvre la porte à l'agrégation de signatures et aux multi-signatures (le schéma MuSig), où plusieurs signataires produisent ensemble une signature unique, aussi compacte qu'une seule. Impossible aussi proprement avec ECDSA.

Schnorr contre ECDSA

Critère	Schnorr	ECDSA
Origine	Fiat-Shamir sur log discret	variante de DSA
Preuve de sécurité	oui (oracle aléatoire)	plus indirecte
Structure	linéaire, additive	non linéaire (inversion modulaire)
Agrégation / multi-sig	native et propre	difficile
Simplicité	très simple	plus lourde
Histoire	brevetée jusqu'en 2008	adoptée par défaut faute de mieux

Une longue éclipse, une renaissance

Pourquoi ce joyau a-t-il si longtemps été ignoré ? Parce que Claus Schnorr l'avait breveté. Pendant que son brevet courait (jusqu'en 2008), l'industrie s'est rabattue sur des alternatives libres de droits, notamment DSA puis ECDSA — techniquement inférieures sur bien des points, mais utilisables sans licence.

Le brevet expiré, l'intérêt est revenu. Le couronnement est arrivé en 2021 : Bitcoin a adopté les signatures de Schnorr via la mise à jour Taproot. Leur linéarité permet d'agréger les signatures d'une transaction à plusieurs participants en une seule, améliorant à la fois la confidentialité et la taille des blocs. Un algorithme de 1989, longtemps mis de côté, se retrouve au cœur de l'une des infrastructures les plus scrutées de la planète.

En résumé