Cryptography Reference
In-Depth Information
n
, the function f
s
is defined such that
follows. For every s
∈{
0, 1
}
G
σ
n
···
G
σ
2
G
σ
1
(x)
···
f
s
(x)
def
=
where s
=
σ
1
···σ
n
and G
σ
is as in Construction 3.6.5. Namely, the roles of x and s
in Construction 3.6.5 are switched (i.e., the root of the tree is labeled by x, and the
value of f
s
on x is obtained by following the path corresponding to the index s). Prove
that the resulting function ensemble is not necessarily pseudorandom (even if G is a
pseudorandom generator).
Guideline:
Show, first, that if pseudorandom generators exist, then there exists a pseu-
dorandom generator Gsatisfying G(0
n
)
0
2n
.
=
Exercise 27:
Pseudorandomgeneratorswithdirectaccess:Adirect-accesspseudo-
random generator is a deterministic polynomial-time algorithm G for which no proba-
bilistic polynomial-time oracle machine can distinguish the following two cases:
1.
New queries of the oracle machine are answered by independent flips of an unbiased
coin. (Repeating the same query twice yields the same answer.)
2.
First, a random “seed” sof length nis uniformly chosen. Next, each query qis answered
by G(s, q).
The bit G(s, i) can be thought of as the ith bit in a bit sequence corresponding to the
seed s, where i is represented in binary.
Prove that the existence of (ordinary) pseudorandom generators implies the exis-
tence of pseudorandom generators with direct access.
Guideline:
A pseudorandom generator with direct access is essentially a pseudoran-
dom function ensemble.
Show that modifying this definition, so that only unary queries are allowed, will yield
an alternative definition of a relaxed on-line pseudorandom generator (as defined in
Exercise 21).
Guideline:
Given a next-step function gof a relaxed on-line pseudorandom generator,
we obtain a generator G supporting “direct access” to a polynomially long sequence
by letting G(s,1
i
) be the ith bit produced by the relaxed on-line generator on initial
state s. Conversely, given such a “unary direct-access” machine G, we obtain a next-
step function gby letting g(s,1
i
)
=
(G(s,1
i
+
1
), (s,1
i
+
1
)). (That is, the ith state is (s,1
i
),
where s
≡
(s,
λ
) is the initial state.)
Evaluate the advantage of direct-access pseudorandom generators over on-line
pseudorandom generators even in settings requiring direct access only to bits of
apolynomiallylongpseudorandomsequence.
Exercise 28:
Consider pseudorandom function ensembles as defined in Definition
3.6.4, with respect to a length function
.
1.
Show that for
(n)
>
log
2
n, any such pseudorandom function gives rise to a pseudoran-
dom generator. In fact, it suffices to have
(n)
(n)
:
N
→
N
>
n.
2.
For
(n)
(n)
≤
n, present a construction of a pseudorandom function ensembles with length
:
N
→
N
, without relying on any assumptions.
Exercise 29:
Let
{
f
s
:
{
0, 1
}
}
|
s
|
}
s
∈{
0,1
}
∗
be a generalized pseudoran-
dom function ensemble, and suppose that G
is polynomial-time-computable and that
d(
|
s
|
)
→{
0, 1
