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 }_{\mathsf{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 and succinct arguments.

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. They constructed a 3-round public-coin identification scheme that is secure in the ROM, yet whose Fiat-Shamir transform is existentially forgeable under every concrete hash function. This demonstrates that the random oracle cannot always be replaced by an actual hash function, even a cryptographically strong one.

${\mathbf{Adv}}_{{\Pi }_H,\mathcal{A}}^{\mathrm{uf}}(\lambda )\ge 1-\mathrm{negl}(\lambda )\text{for all }H.$

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. This raises serious questions about the security of deployed non-interactive succinct arguments based on Fiat-Shamir.