HVCZK = CZK

Equivalence · Vad06

Statement

Every language with an interactive proof that is computational zero-knowledge against the honest verifier has a computational zero-knowledge proof against every efficient verifier, so $\mathbf{HVCZK}=\mathbf{CZK}$, unconditionally — Vad06. The inclusion $\mathbf{CZK}\subseteq \mathbf{HVCZK}$ holds by definition.

Notes

• The equality concerns the class and need not preserve round complexity — Vad06. The companion equality of black-box and general simulators in Vad06 is therefore consistent with the round-restricted black-box bounds, such as Three-message black-box ZK ⊆ BPP — GK96a.
• Vad06 also show that public-coin CZK equals CZK, that CZK is closed under union, and that every problem in CZK decomposes into a problem in SZK together with a set of instances from which a one-way function can be built — Vad06.
• The statistical analogue is HVSZK = SZK — GSV98.