From interactive to signature

The Fiat-Shamir transform

The Schnorr protocol has a practical flaw: it requires an online verifier to send the challenge c. Under these conditions, it is impossible to sign a document that someone will read tomorrow. The Fiat-Shamir transform (1986) removes this constraint with a stroke of genius.

The idea: replace randomness with a hash

Where does the challenge c come from? From the verifier, who draws it at random. Its only virtue is being unpredictable to the prover at the moment he chooses t. Fiat and Shamir make the following observation: a hash function is also unpredictable. So let's replace the verifier with a computation:

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

The prover computes his own challenge himself by hashing his own commitment. Since H is unpredictable, he cannot choose t as a function of c (he would need to know c before computing t, whereas c depends on t). The soundness trap therefore stays shut.

Interactive versus non-interactive

   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

The benefit is immense: no more online verifier needed. The prover single-handedly produces a self-sufficient triple. Anyone, later, recomputes c = H(t, m) from the public elements and checks g^s = t * y^c. The interactive proof has become a standalone proof, transmissible and verifiable by everyone.

A general recipe

Fiat-Shamir is not a sleight of hand specific to Schnorr: it is a general recipe. Any protocol of the commitment – challenge – response type can be made non-interactive by replacing the random challenge with the hash of the commitment. It is one of the most universal tools of modern cryptography, at the heart of countless signatures and proof systems (all the way to zk-SNARKs).

The price to pay

This magic has two conditions:

Good randomness. The nonce r remains indispensable and must always be fresh and secret. The transform does not exempt you from the discipline seen in the previous chapter — on the contrary, a reused r remains catastrophic.
The random oracle model. The security proof assumes that H behaves like a perfectly random function (a random oracle). This is an idealization: no real function is entirely so. In practice, with a good function like SHA-256, the construction holds up, but the theoretical guarantee rests on this idealized model.

In summary