期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes no reference to interaction or zero knowledge.
We propose the use of complete problems to unify and extend the study
of statistical zero knowledge. To this end, we examine several
consequences of our Completeness Theorem and its proof, such as:
- A way to make every (honest-verifier) statistical zero-knowledge
proof very communication efficient, with the prover sending only one
bit to the verifier (to achieve soundness error 1/2).
- Simpler proofs of many of the previously known results about
statistical zero knowledge, such as the Fortnow and Aiello--Håstad
upper bounds on the complexity of SZK and Okamoto's result that SZK is
closed under complement.
- Strong closure properties of SZK which amount to constructing
statistical zero-knowledge proofs for complex assertions built out of
simpler assertions already shown to be in SZK.
- New results about the various measures of "knowledge complexity,"
including a collapse in the hierarchy corresponding to knowledge
complexity in the "hint" sense.
- Algorithms for manipulating the statistical difference between
efficiently samplable distributions, including transformations which
"polarize" and "reverse" the statistical relationship between a pair
of distributions.
