Fiat-Shamir Heuristic

The Fiat-Shamir heuristic (or Fiat-Shamir transform) is a technique for compiling a public-coin interactive protocol into a non-interactive one by replacing the verifier’s random challenges with the output of a hash function applied to the transcript so far. The transform is proven secure when the hash function is modeled as a random oracle, but is known to fail in important settings when instantiated with concrete hash functions.

Description

Given a $(2k+1)$-message public-coin interactive protocol $\Pi =(P,V)$ with messages $a_1,c_1,\dots ,a_k,c_k,a_{k+1}$, the Fiat-Shamir transform produces a non-interactive protocol ${\Pi }_{\mathrm{FS}}$ as follows: the prover computes each verifier challenge itself as

$c_i:=H(a_1,c_1,\dots ,a_{i-1},c_{i-1},a_i),$

where $H$ is a hash function modeled as a random oracle. The resulting proof $(a_1,c_1,\dots ,a_{k+1})$ can be verified by any party who recomputes the same hash challenges.

The transform is particularly useful for constructing digital signatures from identification schemes (the original application of Fiat and Shamir), and for building non-interactive zero-knowledge proofs. It creates no succinctness, since the proof is the prover’s transcript; applied to a PCP or a public-coin IOP whose oracles are Merkle-committed, it yields succinct non-interactive arguments in the random oracle model — Mic00, BCS16 (for IOPs, given state-restoration soundness).

Security in the ROM

In the random oracle model, the Fiat-Shamir transform preserves soundness and zero-knowledge (and simulation-extractability) for a broad class of protocols. This is the primary justification for its widespread use.

Known Failures

Standard Model (GK03)

Goldwasser and Kalai showed that the Fiat-Shamir transform is uninstantiable in the standard model GK03: there is a secure 3-round public-coin identification scheme $\Pi$ whose Fiat-Shamir signature scheme is secure in the ROM, yet for every efficient $H$ there is an efficient $\mathcal{A}$ with

${\mathbf{Adv}}_{{\Pi }_{\mathrm{FS}}^H,\mathcal{A}}^{\mathrm{euf}\text{-}\mathrm{cma}}(\lambda )\ge 1-\mathrm{negl}(\lambda ),$

where ${\Pi }_{\mathrm{FS}}^H$ is the transform of $\Pi$ with $H$ in place of the oracle. This demonstrates that the random oracle cannot always be replaced by an actual hash function, even a cryptographically strong one.

Natural Protocols (KRS25)

Prior counterexamples to Fiat-Shamir were contrived — protocols specifically engineered to fail. Khovratovich, Rothblum, and Soukhanov gave the first counterexample for a standard, widely-studied protocol KRS25. They showed that the Fiat-Shamir transform applied to the GKR succinct interactive argument (from GKR15) allows an efficient prover to prove false statements for explicit families of circuits.

Participates in

Barriers

• No fixed-construction reduction from Fiat-Shamir + GKR to SNARK
• No fixed-construction reduction from Fiat-Shamir + Hash function to DS
• No fixed-construction reduction from Fiat-Shamir to NIZK

Used via Fiat-Shamir Heuristic

• HVZK ⇒ NIZK (Fiat–Shamir)
• Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir)