A Complete Problem for Statistical Zero Knowledge
Amit Sahai and Salil Vadhan
Abstract
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.
Versions
-
Proceedings of 38th Annual Symposium on Foundations of Computer Science,
pp. 448-457, Miami Beach, FL, October 1997. IEEE.
-
See also Manipulating
Statistical Difference (material merged into full version of this paper).
-
Cryptology ePrint Archive Report 2000/056.
Electronic Colloquium on Computational Complexity TR00-084.
-
Journal of the ACM, Vol. 50, No. 2, April 2003, pages 1-54. [ postscript
][ pdf ][official
JACM page]
[
back to Salil Vadhan's research interests ]