Cryptography Reference
In-Depth Information
polynomial-size circuits D
def
=
{
D
n
}
n
∈
N
such that for every n,
D
(n)
≥
C
(n)
where
D
(n)
def
=
|
Pr [D
n
(X
n
)
1]
−
Pr [D
n
(Y
n
)
1]
|
=
=
C
(n)
def
=
|
Pr [C
n
(X
n
)
=
1]
−
Pr [C
n
(Y
n
)
=
1]
|
Exercise 9:
Computational indistinguishability by circuits, single sample versus sev-
eral samples: Prove that X
Y
n
}
n
∈
N
are indistinguishable by
polynomial-size circuits (as per Definition 3.2.7) if and only if their m(
=
{
X
n
}
n
∈
N
and Y
=
{
·
)-products are
indistinguishable by polynomial-size circuits, for every polynomial m(
·
). We stress that
X and Y need not be polynomial-time-constructible.
Guideline:
A “good choice” of x
1
,...,x
k
and y
k
+
2
,..., y
m
can be “hard-wired” into the
circuit.
Exercise 10:
Computationalindistinguishability,circuitsversusalgorithms:
1.
(Easy) Suppose that the ensembles X
Y
n
}
n
∈
N
are indistinguish-
able by polynomial-size circuits. Prove that they are computationally indistinguishable (by
probabilistic polynomial-time algorithms).
Guideline:
Use Exercise 8.
2.
(Hard) Show that there exist ensembles that are computationally indistinguishable (by
probabilistic polynomial-time algorithms), but are distinguishable by polynomial-size
circuits.
Guideline (Part 2):
Given any function f :
{
0, 1
}
∗
→
[0, 1], prove the existence of
an ensemble X
=
{
X
n
}
n
∈
N
such that each X
n
has support of size at most 2 and
yet Pr [f(X
n
)
=
1]
=
Pr [f(U
n
)
=
1], where U
n
is uniformly distributed over
{
0, 1
}
=
{
X
n
}
n
∈
N
and Y
=
{
n
.
Generalize the argument so that given t such functions, f
1
,..., f
t
:
{
0, 1
}
∗
→
[0, 1],
each X
n
has support of size at most t
+
1 and yet Pr [f
i
(X
n
)
=
1]
=
Pr [f
i
(U
n
)
=
1] for
each i
=
1,...,t. (Extra hint: Consider the t-dimensional vectors (f
1
(x),..., f
t
(x)) for
each x
∈{
0, 1
}
n
and think of convex hulls.) A standard diagonalization argument will
finish the job. (In case you did not get it, consult [111].)
Exercise 11:
Prove that the existence of a pair of polynomial-time-constructible en-
sembles that are computationally indistinguishable and are not statistically close implies
the existence of one-way functions.
Guideline:
We seek a simpler proof than one presented earlier [93], where it was proved
that the hypothesis implies the existence of pseudorandom generators. Still, the main
idea of that proof should be applied: Taking sufficiently many independent copies of each
ensemble, construct two computationally indistinguishable ensembles that are “almost
disjoint” (i.e., have statistical difference at least 1
−
2
−
n
). Next, assuming for a moment
that the ensembles are disjoint (i.e., have statistical difference 1), prove the conclusion
of this exercise (by using a variant of the proof of Proposition 3.3.8). Finally, deal with
the general case by using an analogous argument in order to show that the hypoth-
esis implies the existence of a “distributionally one-way function” as in Exercise 17 of
Chapter 2.
