Statistical zero-knowledge (SZK)

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).

Known relationships

  • Graph non-isomorphism is in SZK
  • SZK is closed under complement
  • SZK is contained in AM intersect coAM