Cryptography Reference
In-Depth Information
Exercise 2:
Computationalindistinguishabilityispreservedbyefficientalgorithms: Let
{
Y
n
}
n
∈
N
be two ensembles that are polynomial-time-indistinguishable.
1.
For any probabilistic polynomial-time algorithm A, prove that the ensembles
{
A(X
n
)
}
n
∈
N
and
{
A(Y
n
)
}
n
∈
N
are polynomial-time-indistinguishable.
2.
Show that if Ais not polynomial-time, then
{
A(X
n
)
}
n
∈
N
and
{
A(Y
n
)
}
n
∈
N
are notnecessarily
polynomial-time-indistinguishable.
X
n
}
n
∈
N
and
{
Exercise 3:
Statistical closeness is preserved by any function: Let
{
X
n
}
n
∈
N
and
{
Y
n
}
n
∈
N
be two ensembles that are statistically close, and let f :
{
0, 1
}
∗
→{
0, 1
}
∗
be a function. Prove that the ensembles
{
f(X
n
)
}
n
∈
N
and
{
f(Y
n
)
}
n
∈
N
are statistically
close.
Exercise 4:
Prove that for every L
∈
BPP
and every pair of polynomial-time-
indistinguishable ensembles
{
X
n
}
n
∈
N
and
{
Y
n
}
n
∈
N
, it holds that the function
L
(n)
def
=
|
Pr[X
n
∈
L]
−
Pr[Y
n
∈
L]
|
is negligible in n.
It is tempting to think that the converse holds as well, but we do not know whether
or not it does; note that
can be distinguished by a probabilistic algo-
rithm, but not by a deterministic one. In such a case, which language should we de-
fine? For example, suppose that Ais a probabilistic polynomial-time algorithm, and let
L
def
{
X
n
}
and
{
Y
n
}
1
2
}
. Then L is not necessarily in
BPP
. (Exercise 5 shows that
in the non-computational setting both the foregoing and its converse are true.)
=
{
x :Pr[A(x)
=
1]
≥
Exercise 5:
Anequivalentformulationofstatisticalcloseness: Prove that two ensem-
bles,
}
∗
,
{
X
n
}
n
∈
N
and
{
Y
n
}
n
∈
N
, are statistically close if and only if for every set S
⊆{
0, 1
S
(n)
def
=
|
Pr [X
n
∈
S]
−
Pr [Y
n
∈
S]
|
is negligible in n.
Guideline:
Show that the statistical difference between X
n
and Y
n
, as defined in Eq. (3.1),
equals max
S
{
S
(n)
}
.
Exercise 6:
Statisticalclosenessimpliescomputationalindistinguishability: Prove that
if two ensembles are statistically close, then they are polynomial-time-indistinguishable.
Guideline:
Use the result of Exercise 5, and define for every function f :
{
0, 1
}
∗
→{
0, 1
}
def
=
{
a set S
f
x : f(x)
1
}
.
=
Exercise 7:
An information-theoretic analogue of Theorem 3.2.6: Prove that if two
ensembles are statistically close, then their polynomial products must be statistically
close.
Guideline:
Show that the statistical difference between the m-products of two distributions
is bounded by m times the distance between the individual distributions.
Exercise 8:
Computational indistinguishability by circuits, probabilism versus deter-
minism: Let
Y
n
}
n
∈
N
be two ensembles, and let C
def
C
n
}
n
∈
N
be a family
of probabilistic polynomial-size circuits. Prove that there exists a family of (deterministic)
{
X
n
}
n
∈
N
and
{
=
{
