Cryptography Reference
In-Depth Information
In this definition,
y
represents a priori information to the prover, whereas
z
represents
a priori information to the verifier. Both
y
and
z
may depend on the common input
x
;
for example, if
y
facilitates the proving task, then
y
must depend on
x
(e.g., in case
y
is an
NP
-witness for
x
∈
L
∈
NP
). We stress that the local inputs (i.e.,
y
and
z
) may
not be known, even in part, to the other party. We also stress that the auxiliary input
z
(but not
y
) is also given to the distinguishing algorithm (which can be thought of as an
extension of the verifier).
Recall that by Definition 4.2.10, saying that the interactive machine
V
∗
is proba-
bilistic polynomial-time means that its running time is bounded by a polynomial in
the length of the common input. Hence, the verifier program, the simulator, and the
distinguishing algorithm all run in time polynomial in the length of
x
(and not in time
polynomial in the total length of all their inputs). This convention is essential in many
respects (unless one explicitly bounds the length of the auxiliary input by a polynomial
in the length of
x
; see Exercise 11). For example, having allowed the distinguishing
algorithm to run in time proportional to the length of the auxiliary input would have
collapsed computational zero-knowledge to perfect zero-knowledge (e.g., by consider-
ing verifiers that run in time polynomial in the common input, yet have huge auxiliary
inputs of length exponential in the common input).
Definition 4.3.10 refers to computational zero-knowledge. A formulation of perfect
zero-knowledge with respect to auxiliary input is straightforward. We remark that the
perfect zero-knowledge proof for Graph Isomorphism, presented in Construction 4.3.8,
is in fact perfect zero-knowledge with respect to auxiliary input. This fact follows easily
by a minor augmentation to the simulator constructed in the proof of Proposition 4.3.9
(i.e., when invoking the verifier, the simulator should provide it the auxiliary input that is
given to the simulator). In general, a demonstration of zero-knowledge can be extended
to yield zero-knowledge with respect to auxiliary input whenever the simulator used
in the original demonstration works by invoking the verifier's program as a black box
(see Definition 4.5.10 in Section 4.5.4). All simulators presented in this topic have this
property.
Advanced Comment: Implicit Non-Uniformity in Definition 4.3.10
The non-uniform nature of Definition 4.3.10 is captured by the fact that the distinguisher
gets an auxiliary input. It is true that this auxiliary input is also given to both the verifier
program and the simulator; however, if the auxiliary input is sufficiently long, then only
the distinguisher can make use of its suffix (since the distinguisher may be determined
after the polynomial-time bound of the simulator is fixed). It follows that the simula-
tor guaranteed in Definition 4.3.10 produces output that is indistinguishable from the
real interactions also by non-uniform polynomial-size circuits (see Definition 3.2.7).
Namely, for every (even non-uniform) polynomial-size circuit family
{
C
n
}
n
∈N
,ev-
ery polynomial
p
(
·
), all sufficiently large
n
's, all
x
∈
L
∩{
0
,
1
}
n
, all
y
∈
P
L
(
x
), and
z
∈{
0
,
1
}
∗
,
1
p
(
|
x
|
)
V
∗
(
z
)
M
∗
(
x
|
Pr
[
C
n
(
x
,
z
,
P
(
y
)
,
(
x
))
=
1]
−
Pr
[
C
n
(
x
,
z
,
,
z
))
=
1]
|
<
