Cryptography Reference
In-Depth Information
Let ( P , V ) be an interactive proof system for some language L . We say that ( P , V ),
or actually P ,is perfect zero-knowledge if for every probabilistic polynomial-time
interactive machine V there exists an ( ordinary ) probabilistic polynomial-time
algorithm M such that for every x L the following two random variables are
identically distributed:
P , V ( x ) (i.e., the output of the interactive machine V after interacting with
the interactive machine P on common input x )
M ( x ) (i.e., the output of machine M on input x )
Machine M is called a simulator for the interaction of V with P .
We stress that we require that for every V interacting with P , not merely for V , there
exists a (“perfect”) simulator M . This simulator, although not having access to the
interactive machine P , is able to simulate the interaction of V with P . The fact that
such simulators exist means that V does not gain any knowledge from P (since the
same output could be generated without any access to P ).
The Simulation Paradigm
The foregoing discussion follows a general definitional paradigm that is also used in
other chapters of this topic (specifically, in Volume 2). The simulation paradigm postu-
lates that whatever a party can do by itself cannot be considered a gain from interaction
with the outside. The validity of this paradigm is evident, provided we bear in mind
that by “doing” we mean “efficiently doing” something (and more so if the complexity
of “doing it alone” is tightly related to the complexity of “doing it after interaction with
the outside”). 6 Admittedly, failure to provide a simulation of an interaction with the
outside does NOT necessarily mean that this interaction results in some “real gain” (in
some intuitive sense). Yet what matters is that any “real gain” can NOT occur whenever
we are able to present a simulation. In summary, the approach underlying the simula-
tion paradigm may be overly cautious, but it is certainly valid. (Furthermore, to say the
least, it seems much harder to provide a robust definition of “real gain.”)
BPP
Trivial Cases. Note that every language in
has a perfect zero-knowledge proof
system in which the prover does nothing (and the verifier checks by itself whether
to accept or reject the common input). To demonstrate the zero-knowledge property
of this “dummy prover,” one can present for every verifier V a simulator M that is
essentially identical to V (except that the communication tapes of V , which are never
used, are considered as ordinary work tapes of M ).
4.3.1.1. Perfect Zero-Knowledge
Unfortunately, the preceding formulation of (perfect) zero-knowledge is slightly too
strict (at least as far as we know). 7 We relax the formulation by allowing the simulator
to fail, with bounded probability, to produce an interaction.
6 See the discussion of knowledge tightness in Section 4.4.4.2.
7 That is, we do not know of any non-trivial case in which that requirement is satisfied. In contrast, non-
trivial cases satisfying the relaxed definition given next are known, and we actually present one (i.e., a perfect
zero-knowledge proof for Graph Isomorphism).
Search WWH ::




Custom Search