OWF + IP ⇒ CZK

Free reduction · standard model · BGG+90, HILL99, Naor91

Statement

If one-way functions exist, every language with an interactive proof has a computational zero-knowledge interactive proof, so $\mathbf{IP}\subseteq \mathbf{CZK}$ and hence $\mathbf{CZK}=\mathbf{IP}$ — BGG+90. BGG+90 assume a secure probabilistic encryption scheme, used as a bit commitment; a statistically binding bit commitment suffices, and any one-way function yields one — HILL99, Naor91.

Sketch

Start from a public-coin interactive proof for the language, which exists by GS86. The prover sends statistically binding commitments to its messages instead of the messages; the verifier’s coins are public, so it can still send them. At the end, the prover proves in zero knowledge the $\mathbf{NP}$ statement that the committed messages make the verifier accept — BGG+90.

Notes

• Unconditionally only the converse, CZK ⊆ IP, is known — folklore. An unconditional $\mathbf{IP}\subseteq \mathbf{CZK}$ would give $\mathbf{PSPACE}\subseteq \mathbf{CZK}$, since $\mathbf{IP}=\mathbf{PSPACE}$ (Sha90), and hence $\mathbf{PSPACE}=\mathbf{BPP}$ or auxiliary-input one-way functions exist — OW93.