Cryptography Reference
In-Depth Information
V
∗
. Next, machine
V
∗∗
emulates a
single phase
of the interaction of
V
∗
with
P
Q
(on input
x
), starting with the foregoing contents of the work tape of
V
∗
(instead of starting with an empty work tape). The emulated machine
V
∗
regards
the communication tapes of machine
V
∗∗
as its own communication tapes. When
V
∗
completes the interaction in the current phase, machine
V
∗∗
terminates by
outputting the current contents of the work tape of
V
∗
. Thus, when
z
equals
a possible content of the work tape of
V
∗
after
i
≥
1 phases, the emulated
V
∗
behaves as in the
i
+
1 phase, and the output of
V
∗∗
is distributed as the content
of the work tape of
V
∗
after
i
+
1 phases. Actually, the foregoing description
should be slightly modified to deal with the first phase in the interaction with
P
Q
(i.e., the case
i
=
0 ignored earlier). Specifically,
V
∗∗
copies
z
into the work tape
of
V
∗
only if
z
encodes the content of the work tape of
V
∗
(we assume, without
loss of generality, that the content of the work tape of
V
∗
is encoded differently
from the encoding of an auxiliary input for
V
∗
). In case
z
encodes an auxiliary
input to
V
∗
, machine
V
∗∗
invokes
V
∗
on an empty work tape, and
V
∗
regards the
readable tapes of
V
∗∗
(i.e., common-input tape, random-input tape, and auxiliary-
input tape) as its own. Observe that
Z
(1)
def
=
P
,
V
∗∗
(
z
)
(
x
) describes the content
of the work tape of
V
∗
after the first phase (in the interaction with
P
Q
on common
input
x
and auxiliary input
z
). Likewise, for every
i
=
2
,...,
Q
(
|
x
|
), the random
variable
Z
(
i
)
def
(
x
) describes the content of the work tape of
V
∗
after
i
phases. The claim follows.
=
P
,
V
∗∗
(
Z
(
i
−
1)
)
Because
V
∗∗
is a polynomial-time interactive machine (with auxiliary input)
interacting with
P
, it follows by the lemma's hypothesis that there exists a proba-
bilistic machine that simulates these interactions in time polynomial in the length
of the first input. Let
M
∗∗
denote this simulator.
12
Then for every probabilistic
polynomial-time (in
x
) algorithm
D
, every polynomial
p
(
·
), all sufficiently long
x
∈
L
, and all
z
∈{
0
,
1
}
∗
,wehave
1
p
(
|
x
|
)
V
∗∗
(
z
)
M
∗∗
(
x
|
Pr
[
D
(
x
,
z
,
P
,
(
x
))
=
1]
−
Pr
[
D
(
x
,
z
,
,
z
))
=
1]
|
<
(4.1)
We are now ready to present the construction of a simulator
M
∗
that simulates
the “real” output of
V
∗
after interaction with
P
Q
. We can assume, without loss
of generality, that the output of
V
∗
equals the content of its work tapes at the
end of the interaction (since the output of
V
∗
is probabilistic polynomial-time-
computable from the content of its work tapes at that time). Machine
M
∗
uses the
simulator
M
∗∗
(as a black box).
The simulator
M
∗
:
On input (
x
,
z
), machine
M
∗
sets
z
(0)
=
z
and proceeds in
Q
(
|
x
|
) phases. In the
i
th phase, machine
M
∗
computes
z
(
i
)
by running machine
12
Recall that in the case of perfect zero-knowledge (see Definition 4.3.1) machine
M
∗∗
may halt with no real
output (but rather with output
). However, by sufficiently many repetitions, we can make the probability of this
event exponentially vanishing. In the rest of the exposition, we assume for simplicity that
M
∗∗
always halts with
output.
⊥
