Cryptography Reference
In-Depth Information
Definition 4.3.3 is related to but not equal to the simulator used in Definition 4.3.2 (yet
this fact is not reflected in the text of those definitions). Clearly,
(
x
) can be
computed in (deterministic) polynomial time from view
V
∗
(
x
) for each
V
∗
. Although
that is not always true for the opposite direction, Definition 4.3.3 is equivalent to Def-
inition 4.3.2 (by virtue of the universal quantification on the
V
∗
's; see Exercise 10).
The latter fact justifies the use of Definition 4.3.3, which is more convenient to work
with, although it seems less natural than Definition 4.3.2. An analogous alternative
formulation of perfect zero-knowledge can be obtained from Definition 4.3.1 and is
clearly equivalent to it.
P
,
V
∗
4.3.1.4.
∗
Almost-Perfect (Statistical) Zero-Knowledge
A less drastic (than computational zero-knowledge) relaxation of the notion of perfect
zero-knowledge is the following:
Definition 4.3.4 (Almost-Perfect (Statistical) Zero-Knowledge):
Let
(
P
V
)
be
an interactive proof system for some language L. We say that
(
P
,
V
)
is
almost-
perfect zero-knowledge
(or
statistical zero-knowledge
)
if for every probabilistic
polynomial-time interactive machine V
∗
there exists a probabilistic polynomial-
time algorithm M
∗
such that the following two ensembles are statistically close
as functions of
|
x
|
,
:
{
P
,
V
∗
(
x
)
}
x
∈
L
(i.e., the output of the interactive machine V
∗
after it interacts
with the interactive machine P on common input x )
{
M
∗
(
x
)
}
x
∈
L
(i.e., the output of machine M
∗
on input x ).
That is, the statistical difference between
P
,
V
∗
(
x
)
and M
∗
(
x
)
is negligible in
terms of
|
x
|
.
As in the case of computational zero-knowledge, allowing the simulator to output the
symbol
⊥
(with probability bounded above by, say,
1
2
) and considering the conditional
output distribution (as done in Definition 4.3.1) does not add to the power of Definition
4.3.4; see Exercise 8. It is also easy to show that perfect zero-knowledge implies almost-
perfect zero-knowledge, which in turn implies computational zero-knowledge.
The three definitions (i.e., perfect, almost-perfect, and computational zero-
knowledge) correspond to a natural three-stage hierarchy of interpretations of the no-
tion of “close” pairs of probability ensembles. (In all three cases, the pairs of ensembles
being postulated as being close are
{
P
,
V
∗
(
x
)
}
x
∈
L
and
{
M
∗
(
x
)
}
x
∈
L
.)
1.
The most stringent interpretation of closeness is the requirement that the two ensembles
be identically distributed. This is the requirement in the case of perfect zero-knowledge.
2.
A slightly more relaxed interpretation of closeness is that the two ensembles be statis-
tically indistinguishable (or statistically close). This is the requirement in the case of
almost-perfect (or statistical) zero-knowledge.
3.
A much more relaxed interpretation of closeness, which suffices for all practical purposes,
is that the two ensembles be computationally indistinguishable. This is the requirement
in the case of computational zero-knowledge.
