Cryptography Reference
In-Depth Information
M
∗∗
on input (
x
z
(
i
−
1)
). After
Q
(
) phases are completed, machine
M
∗
stops
,
|
x
|
outputting
z
(
Q
(
|
x
|
))
.
Clearly, machine
M
∗
, as constructed here, runs in time polynomial in its first
input. It is left to show that machine
M
∗
indeed produces output that is com-
putationally indistinguishable from the output of
V
∗
(after interacting with
P
Q
).
Namely:
Claim 4.3.11.2:
For every probabilistic algorithm
D
with running time polyno-
mial in its first input, every polynomial
p
(
·
), all sufficiently long
x
∈
L
, and all
z
∈{
0
,
1
}
∗
,wehave
1
p
(
|
x
|
)
Furthermore, if
P
is perfect zero-knowledge, then
P
Q
,
V
∗
(
z
)
(
x
) and
M
∗
(
x
,
z
)
are identically distributed.
V
∗
(
z
)
M
∗
(
x
|
Pr
[
D
(
x
,
z
,
P
Q
,
(
x
))
=
1]
−
Pr
[
D
(
x
,
z
,
,
z
))
=
1]
|
<
Proof sketch:
We use a hybrid argument (see Chapter 3). In particular, we
define the following
Q
(
), corre-
sponds to the following random process. We first let
V
∗∗
interact with
P
for
i
phases, starting with common input
x
and auxiliary input
z
, and denote by
Z
(
i
)
the output of
V
∗∗
after the
i
th phase. We next repeatedly iterate
M
∗∗
for the
remaining
Q
(
|
x
|
)
−
i
phases. In both cases, we use the output of the previous
phase as auxiliary input to the new phase. Formally, the hybrid
H
(
i
)
is defined as
follows:
|
x
|
)
+
1 hybrids. The
i
th hybrid, 0
≤
i
≤
Q
(
|
x
|
=
M
∗
Q
(
|
x
|
)
−
i
x
,
Z
(
i
)
where the
Z
(
j
)
's are as defined in Claim 4.3.11.1, and where
M
∗
0
(
x
,
z
)
def
H
(
i
)
(
x
,
z
)
def
M
∗
k
(
x
,
z
)
def
=
z
=
M
∗∗
k
−
1
(
x
,
M
∗∗
(
x
,
z
))
for
k
and
=
1
,...,
Q
(
|
x
|
)
−
i
) hybrid (i.e.,
H
(
Q
(
|
x
|
))
(
x
Z
(
Q
(
|
x
|
))
) equals
By Claim 4.3.11.1, the
Q
(
|
x
|
,
z
)
=
(
x
). On the other hand, recalling the construction of
M
∗
,wesee
that the zero hybrid (i.e.,
H
(0)
(
x
,
z
)
=
M
∗
Q
(
|
x
|
)
(
x
,
z
)) equals
M
∗
(
x
,
z
). Hence, all
that is required to complete the proof is to show that all pairs of two adjacent
hybrids are computationally indistinguishable (as this will imply that the extreme
hybrids,
H
(
Q
(
|
x
|
))
and
H
(0)
, are also indistinguishable). To this end, we rewrite the
i
and
i
−
1 hybrids as follows:
H
(
i
)
(
x
,
z
)
=
M
∗
Q
(
|
x
|
)
−
i
x
,
Z
(
i
)
=
V
∗
(
z
)
P
Q
,
V
∗∗
Z
(
i
−
1)
(
x
)
H
(
i
−
1)
(
x
,
z
)
=
M
∗
Q
(
|
x
|
)
−
(
i
−
1)
x
,
Z
(
i
−
1)
=
M
∗
Q
(
|
x
|
)
−
i
x
P
,
,
M
∗
Q
(
|
x
|
)
−
i
x
M
∗∗
x
Z
(
i
−
1)
,
,
where
Z
(
i
−
1)
is as defined in Claim 4.3.11.1.
