A complete promise problem for statistical zero-knowledge

Abstract

We present a complete promise problem for SZK, the class of languages possessing statistical zero-knowledge proofs (against an honest verifier). The problem is to decide whether two efficiently samplable distributions are either statistically close or far apart. This characterizes SZK with no reference to interaction or zero-knowledge. From this theorem and its proof we are able to establish several other results about SZK, knowledge complexity, and efficiently samplable distributions.