Cryptography Reference
In-Depth Information
pseudorandom generator expanding
n
-bit-long seeds into
p
(
n
)-bit-long strings for every
polynomial
p
. The alternative construction is obtained by unfolding this combination.
The resulting construction is appealing per se, and more importantly it serves as a
good warm-up for the construction of pseudorandom generators based on collections
of one-way permutations (presented in Section 3.4.2).
3.4.1.1. The Preferred Presentation
By Theorem 3.3.3 (in Section 3.3.2), it suffices to present a pseudorandom generator
expanding
n
-bit-long seeds into (
n
+
1)-bit-long strings. Assuming that one-way per-
mutations (i.e., 1-1 length-preserving functions) exist, such pseudorandom generators
can be constructed easily. We remind the reader that the existence of a one-way permu-
tation implies the existence of a one-way permutation with a corresponding hard-core
predicate (see Theorem 2.5.2). Thus, it suffices to prove the following, where
x
·
y
denotes the concatenation of the strings
x
and
y
.
Theorem 3.4.1:
Let f be a length-preserving
1-1
(strongly one-way) function,
and let b be a hard-core predicate for
f . Then the algorithm G, defined by
G
(
s
)
def
=
f
(
s
)
·
b
(
s
)
, is a pseudorandom generator.
Clearly,
G
is polynomial-time-computable, and
|
G
(
s
)
|=|
f
(
s
)
|+|
b
(
s
)
|=|
s
|+
1. In-
tuitively, the ensemble
{
f
(
U
n
)
·
b
(
U
n
)
}
n
∈N
is pseudorandom, because otherwise
b
(
U
n
)
could be efficiently predicted from
f
(
U
n
) (in contradiction to the hypothesis). The
proof merely formalizes this intuition.
Actually, we present two alternative proofs. The first proof invokes Theorem 3.3.7
(which asserts that polynomial-time unpredictability implies pseudorandomness) and
thus is confined to show that the ensemble
}
n
∈N
is unpredictable in poly-
nomial time. The second proof directly establishes the pseudorandomness of the
ensemble
{
G
(
U
n
)
}
n
∈N
, but does so by using one of the ideas that appeared in the
proof of Theorem 3.3.7.
{
G
(
U
n
)
First Proof of Theorem 3.4.1:
By Theorem 3.3.7 (specifically, the fact that
polynomial-time unpredictability implies pseudorandomness), it suffices to show
that the ensemble
{
G
(
U
n
)
=
f
(
U
n
)
·
b
(
U
n
)
}
n
∈N
is unpredictable in polynomial
time.
Because
f
is 1-1 and length-preserving, the random variable
f
(
U
n
) is uni-
formly distributed in
{
0
,
1
}
n
. Thus, none of the first
n
bits in
f
(
U
n
)
·
b
(
U
n
)
1
can be predicted better than with probability
2
, regardless of computation time
(since these bits are independently and uniformly distributed in
{
0
,
1
}
). What
can be predicted (and actually determined) in exponential time is the
n
+
1 bit of
f
(
U
n
)
·
b
(
U
n
) (i.e., the bit
b
(
U
n
)). However, by the hypothesis that
b
is a hard-core
of
f
, this bit (i.e.,
b
(
U
n
)) cannot be predicted from the
n
-bit prefix (i.e.,
f
(
U
n
))
in polynomial time. A more rigorous argument follows.
We use a reducibility argument. Suppose, contrary to our claim, that there exists
an efficient algorithm
A
that on input (1
n
+
1
,
G
(
U
n
)) reads a prefix of
G
(
U
n
) and
