Cryptography Reference
In-Depth Information
Using an averaging argument, it follows that if an algorithm
D
distingui-
shes the hybrids
H
(
i
)
(
x
z
), then there exists a
z
(in the support
of
Z
(
i
−
1)
) such that algorithm
D
distinguishes the random variables
M
∗
Q
(
|
x
|
)
−
i
(
x
,
P
,
V
∗∗
(
z
)
(
x
)) and
M
∗
Q
(
|
x
|
)
−
i
(
x
,
M
∗∗
(
x
,
z
)) at least as well. (In all
cases,
D
is also given
x
and
z
.) Using algorithms
M
∗∗
and
D
,wegetanew
algorithm
D
, with running time polynomially related to the former algorithms,
that distinguishes the random variables (
x
,
z
,
i
,
z
,
P
,
V
∗∗
(
z
)
(
x
)) and (
x
,
z
,
i
,
z
,
M
∗∗
(
x
,
z
)) at least as well. Specifically, on input (
x
,
(
z
,
i
,
z
)
,α
) (where
α
is taken
either from
P
,
V
∗∗
(
z
)
(
x
) or from
M
∗∗
(
x
,
z
)), algorithm
D
invokes
D
on input
(
x
,
z
,
M
∗
Q
(
|
x
|
)
−
i
(
x
,α
)) and outputs whatever
D
does. Clearly,
z
) and
H
(
i
−
1)
(
x
,
,
|
Pr
[
D
(
x
,
(
z
,
i
,
z
)
,
P
,
V
∗∗
(
z
)
(
x
))
=
1]
−
Pr
[
D
(
x
,
(
z
,
i
,
z
)
,
M
∗∗
(
x
,
z
))
=
1]
|
≥|
Pr
H
(
i
)
(
x
−
Pr
H
(
i
−
1)
(
x
[
D
(
x
,
z
,
,
z
))
=
1]
[
D
(
x
,
z
,
,
z
))
=
1]
|
D
uses
z
),
Note
that
additional
input
(
x
,
z
,
i
,
whereas
it
distinguishes
z
). This does not fit the definition of a distinguisher
for (auxiliary-input) zero-knowledge, as the latter is to be given only (
x
V
∗∗
(
z
)
(
x
) from
M
∗∗
(
x
P
,
,
z
) and
the string to be distinguished. In other words, we have actually constructed a
non-uniform
D
=
D
i
,
z
that, depending on
i
and
z
, distinguishes
P
,
V
∗∗
(
z
)
(
x
)
from
M
∗∗
(
x
,
z
). Still, in the case of perfect zero-knowledge, letting
D
be an ar-
bitrary function (rather than an efficient algorithm), this suffices for contradicting
the hypothesis that
M
∗∗
perfectly simulates (
P
,
V
∗∗
). For the case of compu-
tational zero-knowledge, we use the fact that the definition of auxiliary-input
zero-knowledge implies robustness against non-uniform (polynomial-size) dis-
tinguishers, and we note that
D
i
,
z
falls into this category (provided that
D
also
does). Thus, in both cases, contradiction (to the hypothesis that
M
∗∗
simulates
(
P
,
V
∗∗
)) follows.
,
Further details concerning the proof of Claim 4.3.11.2:
At this stage
(assuming the reader has gone through Chapter 3), the reader should be able to
transform the foregoing proof sketch into a detailed proof. The main thing that
is missing is the detail concerning the way in which an algorithm contradict-
ing the hypothesis that
M
∗∗
is a simulator for (
P
V
∗∗
) is derived from an algo-
rithm contradicting the statement of Claim 4.3.11.2. These details are presented
next.
We assume, to the contradiction, that there exists a probabilistic polynomial-
time algorithm
D
and a polynomial
p
(
,
·
) such that for infinitely many
x
∈
L
, there
}
∗
such that
exists
z
∈{
0
,
1
1
V
∗
(
z
)
M
∗
(
x
|Pr
[
D
(
x
,
z
,
P
Q
,
(
x
))
=
1]
− Pr
[
D
(
x
,
z
,
,
z
))
=
1]
|
>
p
(
|
x
|
)
It follows that for every such
x
and
z
, there exists an
i
∈{
1
,...,
Q
(
|
x
|
)
}
such that
Pr
D
x
z
)
=
1
−Pr
D
x
z
)
=
1
>
1
H
(
i
)
(
x
H
(
i
−
1)
(
x
,
z
,
,
,
z
,
,
Q
(
|
x
|
)
·
p
(
|
x
|
)
