Cryptography Reference
In-Depth Information
(
n
)
def
where the hybrid
H
(
j
)
's are as defined earlier. Denote
ε
=
1
/
(
Q
(
n
)
·
p
(
n
)).
Combining, as before, the definitions of the
i
and
i
1 hybrids with an averaging
argument, it follows that for each such
x
,
z
, and
i
, there exists a
z
such that
Pr
D
x
−
(
x
))
=
1
M
∗
Q
(
|
x
|
)
−
i
(
x
V
∗∗
(
z
)
,
z
,
,
P
,
−Pr
D
x
z
))
=
1
>ε
M
∗
Q
(
|
x
|
)
−
i
(
x
M
∗∗
(
x
,
z
,
,
,
(
|
x
|
)
This almost leads to the desired contradiction. Namely, the random variables
(
x
z
)) can be distinguished using the
algorithms
D
and
M
∗∗
,
provided we “know” i and z
. But how do we get to
“know”
i
and
z
? The problem is resolved using the fact, pointed out earlier, that
the output of
M
∗∗
should be indistinguishable from the interactions of
V
∗∗
with
P
even with respect to non-uniform polynomial-size circuits. Thus, in order to derive
a contradiction, it suffices to construct a non-uniform distinguisher that incorpo-
rates
i
and
z
in its description. Alternatively, we can incorporate
i
and
z
inanew
auxiliary input, denoted
z
, so that
z
is a prefix of
z
,but
z
looks the same as
z
to both
V
∗
and
M
∗
. Next we shall follow the latter alternative.
Let
T
denote a polynomial upper bound on the time-complexity of both
V
∗
and
M
∗
. Note that for every
z
determined for a pair (
x
z
,
V
∗∗
(
z
)
z
,
M
∗∗
(
x
,
P
,
(
x
)) and (
x
,
,
,
z
), as before, it must
z
|≤
) (since
z
is a possible record of a partial computation of
hold that
|
T
(
|
x
|
M
∗
(
x
z
)). Let
z
=
(
z
T
(
|
x
|
)
−|
z
|
,
denotes
the blank symbol of the work tape). We construct a probabilistic polynomial-time
algorithm
D
that distinguishes (
x
,
i
,
z
), where
i
and
z
are as before (and
z
,
V
∗∗
(
z
)
z
,
M
∗∗
(
x
z
)) for
,
P
,
(
x
)) and (
x
,
,
z
)-tuples. On input (
x
z
,α
the aforementioned (
x
,
z
,
i
,
,
) (where
α
supposedly is in
V
∗∗
(
z
)
V
∗∗
(
z
)
(
x
)or
M
∗∗
(
x
z
)
M
∗∗
(
x
z
)), algorithm
either
P
,
(
x
)
=
P
,
,
=
,
D
first extracts
i
and
z
from
z
. Next, it uses
M
∗∗
to compute
M
∗
Q
(
|
x
|
)
−
i
(
x
β
=
,α
).
Finally,
D
halts with output
D
(
x
). Using the fact that
V
∗∗
and
M
∗∗
cannot
distinguish the auxiliary inputs
z
and
z
,wehave
,
z
,β
[
D
(
x
z
,
V
∗∗
(
z
)
[
D
(
x
z
,
M
∗∗
(
x
z
))
|Pr
,
P
,
(
x
))
=
1]
− Pr
,
,
=
1]
|
[
D
(
x
z
,
V
∗∗
(
z
)
[
D
(
x
z
,
M
∗∗
(
x
z
))
=|Pr
,
P
,
(
x
))
=
1]
− Pr
,
,
=
1]
|
=
Pr
D
x
(
x
))
=
1
V
∗∗
(
z
)
,
z
,
M
Q
(
|
x
|
)
−
i
(
x
,
P
,
−Pr
D
x
z
))
=
1
M
∗∗
(
x
,
z
,
M
Q
(
|
x
|
)
−
i
(
x
,
,
>ε
(
|
x
|
)
Contradiction (to the hypothesis that
M
∗∗
is a simulator for (
P
V
∗∗
)) follows.
,
The lemma follows.
And What About Parallel Composition?
Unfortunately, we cannot prove that zero-knowledge (even with respect to auxiliary
input) is preserved under parallel composition. Furthermore, there exist (auxiliary-
input) zero-knowledge proofs that when played twice in parallel do yield knowledge
(to a “cheating verifier”). For further details, see Section 4.5.4.
The fact that zero-knowledge is not preserved under parallel composition of proto-
cols is indeed bad news. One might even say that this fact is a conceptually annoying
