Statistical zero-knowledge

The class of decision problems for which a “yes” answer can be verified by a statistical zero-knowledge proof protocol. In such an interactive proof (see IP), we have a probabilistic polynomial-time verifier, and a prover who has unbounded computational resources. By exchanging messages with the prover, the verifier must become convinced (with high probability) that the answer is “yes,” without learning anything else about the problem (statistically).

See the complexity zoo entry here.

Known relationships

• Graph non-isomorphism is in SZK — the verifier can check statistical distance between two distributions via the prover
• SZK is closed under complement — GS86
• SZK ⊆ AM ∩ coAM, so if AM = coAM then SZK ⊆ AM; in particular SZK does not contain NP-complete problems unless PH collapses
• Non-trivial SZK implies OWFs: if there is a language in SZK that is not in BPP, then one-way functions exist — Ost91
  • This is a converse direction: SZK ⊄ BPP $\Rightarrow$ OWF exist
• The complete problem for SZK is the Statistical Difference (SD) problem: given two circuits sampling distributions $D_0$ and $D_1$, decide whether $\Vert D_0-D_1{\Vert }_{\mathrm{TV}}\ge 2/3$ or $\le 1/3$