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}$ on a statement $x$, 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(x,a_1,c_1,\dots ,a_{i-1},c_{i-1},a_i),$

where $H$ is a hash function modeled as a random oracle. Omitting $x$ from the hash input lets a prover that chooses the statement pick a false one after computing the challenges — standard; ROM ⇒ SNARK gives an example. 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

For a large class of signature schemes obtained from three-move identification protocols, the forking lemma reduces security in the random oracle model to the hard problem underlying the protocol — PS00. For public-coin interactive oracle proofs, the soundness of the transform in the ROM is tightly characterized by state-restoration soundness, which is bounded tightly in terms of soundness and round complexity (BCS transform) — BCS16. For a $(2\mu +1)$-move public-coin protocol and $Q$ oracle queries the generic loss is approximately $Q^{\mu }$, which the $\mu$-fold sequential repetition of $\Sigma$-protocols attains, while for $(k_1,\dots ,k_{\mu })$-special-sound protocols the knowledge error degrades only linearly in $Q$ — AFK22.

Correlation-intractable instantiation

With a hash family in place of the oracle that is correlation-intractable for the relations given by the protocol’s bad challenges, Fiat-Shamir is sound for protocols with round-by-round soundness, a notion introduced there — CCH+19. CJJ21 instantiate it this way for an interactive batch argument, from LWE (LWE with polynomial ratio ⇒ BARG for NP).

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

• Circular-secure FHE ⇒ NIZK argument for NP
• DLOG ⇒ Schnorr signatures
• HVZK ⇒ NIZK (Fiat–Shamir)
• Low-noise LPN + DDH ⇒ NIZK argument for NP
• LWE ⇒ NIZK
• LWE with polynomial ratio ⇒ BARG for NP
• LWE with polynomial ratio ⇒ SNARG for P
• Schnorr identification ⇒ Schnorr signatures (Fiat–Shamir)
• Sub-exponential DDH ⇒ NIZK argument for NP
• Sub-exponential DDH ⇒ PPAD hardness
• Sub-exponential LWE ⇒ PPAD hardness
• Succinct state-restoration-sound IOP ⇒ STARK (BCS transform)