HVSZK = SZK

Equivalence · GSV98

Statement

Every problem with an honest-verifier statistical zero-knowledge proof has a statistical zero-knowledge proof against all verifiers: $\mathbf{HVSZK}=\mathbf{SZK}$ — GSV98. The inclusion $\mathbf{SZK}\subseteq \mathbf{HVSZK}$ holds by definition.

Notes

• The transformation goes through public-coin honest-verifier protocols, which Okamoto’s analysis provides, and then compiles them against cheating verifiers — GSV98, Oka96.
• Combined with Okamoto’s closure of honest-verifier SZK under complement, this gives SZK = coSZK — Oka96, GSV98.