CRHF ⇒ Constant-round ZK argument (Barak)

Free reduction · standard model · Bar01

Statement

Assuming collision-resistant hash functions, NP has a constant-round public-coin zero-knowledge argument with negligible soundness error whose simulator uses the cheating verifier’s code — Bar01.

Sketch

The prover commits to a program and gives a witness-indistinguishable universal argument that $x\in L$ or the committed program predicts the verifier’s next message; the simulator commits to the verifier’s own code and uses that branch as its witness, with no rewinding.

Notes

• With black-box simulation, only languages in BPP have such protocols (Constant-round public-coin black-box ZK ⊆ BPP) — GK96a.
• The simulator runs in strict polynomial time, which no black-box simulator of a constant-round protocol for a language outside $\mathbf{BPP}$ achieves (Constant-round black-box ZK with strict polynomial-time simulation ⊆ BPP) — BL02.