Welcome to the resource topic for 2000/056
Title:
A Complete Problem for Statistical Zero Knowledge
Authors: Amit Sahai, 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:
(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.
ePrint: https://eprint.iacr.org/2000/056
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .