ID ⇒ DS

Fully-black-box reduction · random oracle model · FS86 · security loss: $\approx {\epsilon }^2/q$ for advantage $\epsilon$ and $q$ random-oracle queries (PS96)

Statement

The Fiat–Shamir transform turns a three-move public-coin identification scheme into a signature scheme in the ROM: the signer computes the verifier’s challenge as the random-oracle hash of the commitment and the message, and the signature is the resulting transcript — FS86. If the identification scheme is secure against impersonation under passive attack and non-trivial (its commitments have super-logarithmic min-entropy), the resulting scheme is EUF-CMA-unforgeable in the ROM; for non-trivial schemes, passive-impersonation security is also necessary — AABN02.

Sketch

The reduction guesses which random-oracle query the forgery will use, sends that query’s commitment to the honest verifier, and programs the oracle’s answer to the verifier’s challenge; it answers signing queries with transcripts from the passive-attack oracle, programming the oracle to match. A forgery then completes the impersonation, at a loss linear in the number of oracle queries.

Notes

• The random oracle cannot be removed in general: some secure identification schemes yield signatures forgeable under every hash-function instantiation — GK03.
• For a three-move public-coin honest-verifier zero-knowledge proof of knowledge for a hard relation, the scheme is EUF-CMA-unforgeable in the ROM: the forking lemma reruns the forger on the same coins, resampling the oracle answers from the forgery’s query onward, to obtain two accepting transcripts sharing the commitment, from which special soundness extracts a witness — PS96, PS00. A forger with advantage $\epsilon$ making $q$ random-oracle queries yields a witness with probability about ${\epsilon }^2/q$ — PS96.
• Schnorr’s protocol for discrete log instantiates the transform (Schnorr identification ⇒ Schnorr signatures): the signature on $m$ is $(c,z)$ with $a=g^r$, $c=\mathsf{H}(a,m)$ and $z=r+cx$, and two accepting transcripts with the same $a$ and distinct challenges give $x=(z-z^{\prime })/(c-c^{\prime })$ — Sch91.
• The same characterization holds for forward security — AABN02.