Cryptography Reference
In-Depth Information
pseudorandom generator with expansion factor
l
1
(
n
)
def
=
n
+
1 can be derived from any
pseudorandom generator.
Each pseudorandom generator, as defined earlier, will have a predetermined ex-
pansion function. In Section 3.3.3 we shall consider “variable-output pseudorandom
generators” that, given a random seed, will produce an infinite sequence of bits such
that every polynomially long prefix of it will be pseudorandom.
3.3.2. Increasing the Expansion Factor
=
n
+
Given a pseudorandom generator
G
1
with expansion factor
l
1
(
n
)
1, we con-
struct a pseudorandom generator
G
with arbitrary polynomial expansion factor as
follows.
Construction 3.3.2:
Let G
1
be a deterministic polynomial-time algorithm map-
ping strings of length n into strings of length n
+
1
, and let p
(
·
)
be a polynomial.
Define G
(
s
)
def
=
σ
i
is the first bit of G
1
(
s
i
−
1
)
, and
s
i
is the
|
s
|
-bit-long suffix of G
1
(
s
i
−
1
)
for every
1
≤
i
≤
p
(
|
s
|
)
. That is, on input s,
algorithm G proceeds as follows:
=
σ
1
···
σ
p
(
|
s
|
)
, where s
0
s, the bit
Let s
0
=
s and n
=|
s
|
.
Fo r i
=
,
do
1
to p
(
n
)
σ
i
s
i
←
G
1
(
s
i
−
1
)
,
where
σ
i
∈{
0
,
1
}
and
|
s
i
|=|
s
i
−
1
|
.
Output
σ
1
σ
2
···
σ
p
(
|
s
|
)
.
The construction is depicted in Figure 3.2: On input
s
, algorithm
G
applies
G
1
for
p
(
|
s
|
)
times, each time on a new seed. Applying
G
1
to the current seed yields a new seed (for
the next iteration) as well as one
extra bit
(which is being output immediately). The seed
in the first iteration is
s
itself. The seed in the
i
th iteration is the
|
s
|
-bit-long suffix of the
string obtained from
G
1
in the previous iteration. Algorithm
G
outputs the concatenation
of the “extra bits” obtained in the
p
(
) iterations. Clearly,
G
is polynomial-time-
computable and expands inputs of length
n
into output strings of length
p
(
n
).
|
s
|
G
. . .
G
G
G
S
0
S
S
S
p(n)
1
1
1
1
2
σ
σ
σ
p(n)
1
2
n
.
Figure 3.2:
Construction 3.3.2, as operating on seed s
0
∈{0, 1}
