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
  • SZK is closed under complement
  • SZK is contained in AM intersect coAM