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:
(1) 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).
(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.
(3) 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.
(4) New results about the various measures of "knowledge complexity," including a collapse in the hierarchy corresponding to knowledge complexity in the "hint" sense.
(5) Algorithms for manipulating the statistical difference between efficiently samplable distributions, including transformations which "polarize" and "reverse" the statistical relationship between a pair of distributions.
Category / Keywords: foundations / statistical zero-knowledge proofs, complexity theory, statistical difference, knowledge complexity, samplable distributions, variation distance Publication Info: Prelimnary versions in FOCS 97 and DIMACS Workshop on Randomization Methods in Algorithm Design (Dec 97) Date: received 30 Oct 2000 Contact author: salil at deas harvard edu Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation Version: 20010309:155444 (All versions of this report) Discussion forum: Show discussion | Start new discussion