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

• The protocol circumvents No reduction from ZKP to Argument systems: with black-box simulation, only languages in BPP have such protocols — GK96a.