SZK = coSZK

Equivalence · Oka96, GSV98

Statement

SZK is closed under complement, $\mathbf{SZK}=\mathbf{coSZK}$: honest-verifier statistical zero-knowledge is closed under complement — Oka96 — and honest-verifier and general statistical zero-knowledge coincide (HVSZK = SZK) — GSV98.

Notes

• A simpler proof goes through the complete problem Statistical Difference — SV03.
• Closure under complement with SZK ⊆ AM gives $\mathbf{SZK}\subseteq \mathbf{AM}\cap \mathbf{coAM}$, so no $\mathbf{NP}$-complete problem lies in SZK unless the polynomial hierarchy collapses — BHZ87.