OWF ⇒ ZKP

Fully-black-box reduction · standard model · GMW91 · security loss: polynomial: soundness is statistical, and 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, every language in $\mathbf{NP}$ has a computational zero-knowledge proof — GMW91. The protocol proves graph 3-colorability with a statistically binding commitment, which one-way functions yield — Naor91, HILL99.

Sketch

The prover commits to a uniformly permuted 3-coloring of the graph; the verifier picks a random edge and the prover opens its two endpoints, which must carry distinct colors. Sequential repetition drives the per-round soundness error $1-1/|E|$ down to a negligible one; a simulator that guesses the challenged edge and rewinds gives computational zero knowledge.