HVZK ⇒ NIZK (Fiat–Shamir)

Fully-black-box reduction · random oracle model · via Fiat–Shamir · FS86 · security loss: soundness: factor $O(q^r)$ over the interactive soundness error for a $q$-query prover and $r$ challenge rounds, $q+1$ for three-move protocols; zero knowledge: the HVZK simulation error plus the probability that a programmed oracle point was queried before

Statement

The Fiat–Shamir transform replaces each verifier challenge of a public-coin protocol by a hash of the statement and the transcript so far — FS86. Applied to a constant-round public-coin interactive proof that is honest-verifier zero-knowledge with negligible soundness error, it yields a NIZK argument in the random-oracle model — standard. For $\Sigma$-protocols the argument is zero-knowledge in the ROM, and with quasi-unique responses it is also simulation-sound and weakly simulation-extractable, hence non-malleable — FKMV12.

Sketch

Zero knowledge: the compiled challenges are uniform, exactly the honest verifier’s, so the simulator runs the HVZK simulator and programs the random oracle to return its challenges. Soundness: each oracle query fixes a prefix before its challenge is revealed, so a $q$-query prover gains at most a $\mathrm{poly}(q)$ factor over the interactive soundness error when the round count is constant.

Notes

• Soundness of the compiled protocol degrades with the number of rounds — standard; beyond constant rounds the transform needs state-restoration soundness of the underlying protocol — BCS16.
• In the standard model the transform can fail: if collision-resistant hash functions exist, there is a 3-round public-coin argument whose transform is unsound for every efficient hash function — GK03 (No fixed-construction reduction from Fiat-Shamir to NIZK).