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 — Okamoto (STOC 1996); simpler proof in SV03
• SZK ⊆ AM ∩ coAM — AH91 (AM), For87 (coAM); in particular SZK does not contain NP-complete problems unless PH collapses — BHZ87
• Average-case-hard SZK implies OWFs: if some language in SZK is hard on average over an efficiently samplable distribution, then one-way functions exist — Ost91
  • From worst-case hardness alone (SZK ⊄ BPP), auxiliary-input one-way functions exist — OW93
• 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$

Participates in

Builds on Statistical zero-knowledge

• SZK ⊆ AM
• SZK ⊆ coAM
• SZK ⊆ CZK
• SZK ⊆ IP
• SZK ⊆ QSZK