Cryptography Reference
In-Depth Information
1.
If for some polynomial p
1
(
·
) and all sufficiently large n's,
β
(n)
<
1
−
(1
/
p
1
(n)), then the
modified definition is equivalent to the original one.
2.
If for some polynomial p
2
(
·
) and all sufficiently large n's,
β
(n)
>
2
−
p
2
(n)
, then the modified
definition is equivalent to the original one.
Justify the bounds placed on the function
β
(
·
).
Guideline:
Invoke the simulator sufficiently many times.
Exercise 7:
Simulator error in perfect zero-knowledge simulators, Part 2: Prove that
Definition 4.3.1 implies Definition 4.3.6.
Exercise 8:
Perfect versus almost-perfect zero-knowledge: Prove that every perfect
zero-knowledge system is also almost-perfect zero-knowledge. (That is, prove that
Definition 4.3.1 implies Definition 4.3.4.)
Guideline:
Using Item 2 of Exercise 6, note that the statistical difference between M
∗
(x)
and m
∗
(x) (i.e., “M
∗
(x) conditioned that it not be
⊥
”) is negligible.
Exercise 9:
Simulator error in computational zero-knowledge simulators: Consider
an alternative to Definition 4.3.2 by which the simulator is allowed to output the symbol
⊥
1
2
) and its output distribution is considered
(with probability bounded above by, say,
conditioned on it not being
(as done in Definition 4.3.1). Prove that this alternative
definition is equivalent to the original one (i.e., to Definition 4.3.2).
⊥
Exercise 10:
Analternativeformulationofzero-knowledge,simulatingtheinteraction:
Prove the equivalence of Definitions 4.3.2 and 4.3.3.
Guideline:
To show that Definition 4.3.3 implies Definition 4.3.2, observe that the output
of every interactive machine can be easily computed from its view of the interaction.
To show that Definition 4.3.2 implies Definition 4.3.3, show that for every probabilistic
polynomial-time V
∗
there exists a probabilistic polynomial-time V
∗∗
such that view
V
∗
(x)
=
P, V
∗∗
(x).
Exercise 11:
Prove that Definition 4.3.10 is equivalent to a version where the auxiliary
input to the verifier is explicitly bounded in length. That is, the alternative zero-knowledge
clause reads as follows:
and for every probabilistic polynomial-time interactive ma-
chine V
∗
there exists a probabilistic polynomial-time algorithm M
∗
such that the
following two ensembles are computationally indistinguishable:
{
P(y
x
), V
∗
(z)
(x)
}
x
∈
L, z
∈{
0,1
}
(
|
x
|
)
{
M
∗
(x, z)
}
x
∈
L,z
∈{
0,1
}
(
|
x
|
)
where y
x
is as in Definition 4.3.10.
Note that it is immaterial here whether the running time of M
∗
(as well as the distin-
guishing gap) is considered as a function of
foreverypolynomial
|
x
|
or as a function of
|
(x, z)
|
.
Exercise 12:
Present a simpleprobabilistic polynomial-time algorithm that simulates
the view of the interaction of the verifier described in Construction 4.3.8 with the prover
defined there. The simulator, on input x
∈
GI, should have output that is distributed
identically to view
P
GI
V
GI
(x).
