Cryptography Reference
In-Depth Information
the oracle on its own input, for every polynomial p(
·
), and for all sufficiently large n's,
Pr
M
F
n
(U
n
)
F
n
(U
n
)
<
1
2
+
1
p(n)
=
That is, unlike the formulation of Exercise 32, the predicting machine cannot select the
point for which it has to predict the value of the function (but rather this point is random
and is given as input).
1.
Show that any pseudorandom function ensemble is weakly unpredictable.
2.
Assuming that pseudorandom function ensembles exist, show that there exists a function
ensemble that is weakly unpredictable, although it is not pseudorandom.
This exercise contradicts a flawed claim (which appeared in earlier versions of this
manuscript). The flaw was pointed out by Omer Reingold.
Guideline:
For Part 1, show that unpredictability, as defined in Exercise 32, implies weak
unpredictability. Alternatively, provide a direct proof (as in Exercise 32). For Part 2, modify
a pseudorandom function ensemble so that each f in the range of F
n
satisfies f(0
n
)
0.
=
Exercise 34:
Anunsuccessfulattempttostrengthenthenotionofweakunpredictabil-
ityoffunctionensemblessothatitisequivalenttopseudorandomnessoffunctions:In
continuation of Exercise 33, suppose that we strengthen the requirement by allowing
the input x to be chosen from any polynomial-time-constructible ensemble. Namely,
here we say that a function ensemble F
F
n
}
n
∈
N
is weakly2 unpredictable if for
every probabilistic polynomial-time oracle machine M that does not query the oracle
on its own input, for every polynomial-time-constructible ensemble
=
{
{
X
n
}
n
∈
N
, where X
n
n
, for every polynomial p(
ranges over
{
0, 1
}
·
), and for all sufficiently large n's,
Pr
M
F
n
(X
n
)
=
F
n
(X
n
)
<
1
2
+
1
p(n)
Again, show that this definition is a necessary but insufficient condition for pseudoran-
dom function ensembles.
Guideline:
Modify the function ensemble so that each f in the range of F
n
satisfies
f( f(a
1
) f(a
2
)
···
f(a
n
))
=
0, where a
1
,...,a
n
n
are some easy-to-compute strings
∈{
0, 1
}
(e.g., a
i
=
0
i
−
1
10
n
−
i
).
Exercise 35:
Let t : N
→
N be such that on input n, one can compute t(n) in poly(n)
time. Let
H
n
}
n
∈
N
be two function ensembles that are indistinguishable by
any probabilistic polynomial-time oracle machine. Prove that the permutation ensembles
{
{
F
n
}
n
∈
N
and
{
DES
t(n)
DES
t(n)
H
n
}
n
∈
N
(defined as in Section 3.7.2) are indistinguishable by
any probabilistic polynomial-time oracle machine. Furthermore, this holds even when
the oracle machine is given access both to the permutation and to its inverse (as in
Definition 3.7.5).
Guideline:
Use a hybrid argument to bridge between the t(n) independent copies of F
n
and the t(n) independent copies of H
n
. The ith hybrid is DES
F
(t(n))
n
F
n
}
n
∈
N
and
{
. Note
,..., F
(i
+
1)
n
, H
(i
n
,..., H
(1)
n
that oracle access to the permutation DES
F
(t(n))
n
(as well as to its inverse)
,..., F
(i
+
2)
n
,g, H
(i
n
,..., H
(1)
n
can be emulated by using oracle access to the function g.
Exercise 36:
Let F
n
and DES
t
F
n
be as in Construction 3.7.6. Prove that regardless of
the choice of the ensemble F
F
n
}
n
∈
N
, the ensemble DES
2
F
n
is notpseudorandom.
182
=
{
