Cryptography Reference
In-Depth Information
4.3.1.5. Complexity Classes Based on Zero-Knowledge
The various definitions of zero-knowledge give rise to natural complexity classes:
Definition 4.3.5 (Class of Languages Having Zero-Knowledge Proofs): We
denote by
ZK
CZK
) the class of languages having (computational) zero-
knowledge interactive proof systems. Likewise,
(also
PZK
SZK
) denotes the
class of languages having perfect ( resp., statistical) zero-knowledge interactive
proof systems.
( resp.,
Clearly,
BPP PZK SZK CZK IP
Assuming the existence of (non-uniformly) one-way functions, the last inclusion is an
equality (i.e.,
CZK = IP
); see Proposition 4.4.5 and Theorems 3.5.12 and 4.4.12. On
the other hand, we believe that the first and third inclusions are strict (as equalities in
either case contradict widely believed complexity assumptions). Thus, our belief is that
BPP PZK SZK CZK = IP
PZK
SZK
The relationship of
to
remains an open problem (with no evidence either
way).
4.3.1.6. Expected Polynomial-Time Simulators
The formulation of perfect zero-knowledge presented in Definition 4.3.1 is different
from the definition used in some early publications in the literature. The original def-
inition requires that the simulator always output a legal transcript (which has to be
distributed identically to the real interaction), yet it allows the simulator to run in
expected polynomial time rather than in strictly polynomial time. We stress that the
expectation is taken over the coin tosses of the simulator (whereas the input to the
simulator is fixed). This yields the following:
Definition 4.3.6 (Perfect Zero-Knowledge, Liberal Formulation): We say that
( P , V ) is perfect zero-knowledge in the liberal sense if for every probabilistic
polynomial-time interactive machine V there exists an expected polynomial-time
algorithm M such that for every x L the random variables P , V ( x ) and
M ( x ) are identically distributed.
We stress that by probabilistic polynomial time we mean a strict bound on the run-
ning time in all possible executions, whereas by expected polynomial time we al-
low non-polynomial-time executions but require that the running time be “polynomial
on the average.” Clearly, Definition 4.3.1 implies Definition 4.3.6 (see Exercise 7).
Interestingly, there exist interactive proofs that are perfect zero-knowledge with re-
spect to the liberal definition but are not known to be perfect zero-knowledge with
respect to Definition 4.3.1. We point out that the naive way of transforming an expected
Search WWH ::




Custom Search