Schnorr signatures and their renaissance

Let's apply the Fiat-Shamir recipe to the Schnorr identification protocol. The result has a name: Schnorr signatures. Long left in the shadows, they are today enjoying a dazzling renaissance.

From identification to signature

The transformation is direct. To sign a message m with its private key 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)]

To verify, with the public key y = g^x:

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

This is exactly Schnorr identification, where the challenge is no longer drawn by a verifier but computed by hashing. The signature binds the message m to the key, and no one can forge it without knowing x.

Three remarkable qualities

Schnorr signatures stand out for three virtues:

• Simplicity. The construction is minimal: one exponentiation, one hash, one addition. Few parts, therefore few things to break.
• Provable security. We know how to prove their security (in the random oracle model), which is not the case for all competing schemes.
• Linearity. This is the most precious property. The response s = r + c*x is linear in x and in r. Two signatures can therefore add together: the s values add up, the commitments combine. This opens the door to signature aggregation and to multisignatures (the MuSig scheme), where several signers together produce a single signature, as compact as one. Not possible so cleanly with ECDSA.

Schnorr versus ECDSA

Critère	Schnorr	ECDSA
Origin	Fiat-Shamir on discrete log	variant of DSA
Security proof	yes (random oracle)	more indirect
Structure	linear, additive	non-linear (modular inversion)
Aggregation / multi-sig	native and clean	difficult
Simplicity	very simple	heavier
History	patented until 2008	adopted by default for lack of better

A long eclipse, a renaissance

Why was this jewel ignored for so long? Because Claus Schnorr had patented it. While his patent ran (until 2008), the industry fell back on royalty-free alternatives, notably DSA then ECDSA — technically inferior on many points, but usable without a license.

With the patent expired, interest returned. The crowning moment came in 2021: Bitcoin adopted Schnorr signatures via the Taproot upgrade. Their linearity makes it possible to aggregate the signatures of a multi-party transaction into a single one, improving both privacy and block size. A 1989 algorithm, long set aside, finds itself at the heart of one of the most scrutinized infrastructures on the planet.

In summary

By applying Fiat-Shamir to Schnorr, we obtain signatures that are simple, provably secure and above all linear, hence aggregatable (MuSig). Long held back by a patent in favor of ECDSA, they are reborn today — even powering Bitcoin since Taproot in 2021.