Cryptography Reference
In-Depth Information
each of the Q
(
)
phases.) Then P
Q
is zero-knowledge (with respect to auxiliary
input) on L. Furthermore, if P is perfect zero-knowledge (with respect to auxiliary
input), then so is P
Q
.
|
x
|
The convention concerning the end-of-proof symbol is introduced for technical pur-
poses (and is redundant in all known proof systems, and furthermore whenever the
number of messages sent during the execution is easily computed from the common
input). Clearly, every machine
P
can be easily modified so that its last message will
bear an appropriate symbol (as assumed earlier), and doing so will preserve the zero-
knowledge properties of
P
(as well as the completeness and soundness conditions).
The lemma ignores other aspects of repeating an interactive proof several times,
specifically, the effect on the gap between the acceptance probabilities for inputs inside
and outside of the language. The latter aspect of repeating an interactive proof system
is discussed in Section 4.2.1.3 (see also Exercise 1).
Proof:
Let
V
∗
be an
arbitrary
probabilistic polynomial-time interactive machine
interacting with the composed prover
P
Q
. Our task is to construct a (polynomial-
time) simulator
M
∗
that will simulate the real interactions of
V
∗
with
P
Q
.
Following is a very high level description of the simulation. The key idea is
to simulate the real interaction on common input
x
in
Q
(
) phases correspond-
ing to the phases of the operation of
P
Q
. Each phase of the operation of
P
Q
is
simulated using the simulator guaranteed for the atomic prover
P
. The informa-
tion accumulated by the verifier in each phase is passed to the next phase using
the auxiliary input.
|
x
|
(In the following exposition, we ignore the auxiliary input to the prover. This merely
simplifies our notation. That is, instead of writing
P
(
y
) and
P
Q
(
y
), where
y
is the
prover's auxiliary input, we write
P
and
P
Q
.)
The first step in carrying out this plan is to partition the execution of an arbitrary
interactive machine
V
∗
into phases. The partition may not exist in the code of the
program
V
∗
, and yet it can be imposed on the executions of this program. This
is done using the phase structure
of the prescribed prover P
Q
, which in turn is
induced by the end-of-proof symbols. Hence, we claim that no matter how
V
∗
operates, the interaction of
V
∗
with
P
Q
on common input
x
can be captured by
Q
(
) successive interactions of a related machine, denoted
V
∗∗
, with
P
. Namely:
|
x
|
Claim 4.3.11.1:
There exists a probabilistic polynomial-time
V
∗∗
such that for
every common input
x
and auxiliary input
z
, it holds that
P
Q
,
V
∗
(
z
)
(
x
)
=
Z
(
Q
(
|
x
|
))
where
Z
(0)
def
=
z
and
Z
(
i
+
1)
def
=
P
,
V
∗∗
Z
(
i
)
(
x
) for
i
=
0
,...,
Q
(
|
x
|
)
−
1
Namely,
Z
(
Q
(
|
x
|
))
is a random variable describing the output of
V
∗∗
after
Q
(
) suc-
cessive interactions with
P
, on common input
x
, where the auxiliary input of
V
∗∗
in the
i
+
1 interaction equals the output of
V
∗∗
after the
i
th interaction (i.e.,
Z
(
i
)
).
217
|
x
|
