OWF ⇒ CZK

Fully-black-box reduction · standard model · GMW91 · security loss: polynomial: zero knowledge reduces to commitment hiding by a hybrid over the polynomially many unopened commitments, on top of the polynomial loss of the commitment from the one-way function

Statement

If one-way functions exist, Graph 3-Coloring, and hence every language in $\mathbf{NP}$, has a computational zero-knowledge interactive proof, so $\mathbf{NP}$ is contained in CZK — GMW91. GMW91 state the protocol for a generic bit commitment; a computationally hiding, statistically binding one suffices, and any one-way function yields one — HILL99, Naor91.

Sketch

Each round the prover commits to a uniformly re-permuted 3-coloring, the verifier names a random edge, and the prover opens its two endpoints, which must carry distinct colors. If the graph is not 3-colorable, every assignment of the three colors to its vertices has a monochromatic edge, so by binding a cheating prover is caught with probability at least $1/|E|$ per round, and sequential repetition makes the soundness error negligible. A simulator that guesses the edge, commits to a coloring valid only there, and rewinds on a wrong guess gives zero knowledge from commitment hiding.