Cryptography Reference
In-Depth Information
applications (and especially in cryptography)
it is desirable to generate pseudorandom
ensembles using as little true randomness as possible
. This leads to the definition of a
pseudorandom generator.
3.3.1. Standard Definition of Pseudorandom Generators
Definition 3.3.1 (Pseudorandom Generator, Standard Definition): A pseudo-
random generator
is a deterministic polynomial-time algorithm G satisfying the
following two conditions:
1.
Expansion:
There exists a function l
:
N → N
such that l
(
n
)
>
n for all n
∈ N
,
|
|=
|
|
∈{
,
}
∗
.
and
G
(
s
)
l
(
s
)
for all s
0
1
2.
Pseudorandomness:
The ensemble
{
G
(
U
n
)
}
n
∈N
is pseudorandom.
The function l is called the
expansion factor
of G.
The input
s
to the generator is called its
seed
. The expansion condition requires that
the algorithm
G
map
n
-bit-long seeds into
l
(
n
)-bit-long strings, with
l
(
n
)
>
n
. The
pseudorandomness condition requires that the output distribution induced by applying
algorithm
G
to a uniformly chosen seed be polynomial-time-indistinguishable from a
uniform distribution, although it is
not
statistically close to uniform. Specifically, using
Exercise 5 (for the first equality), we can bound the statistical difference between
G
(
U
n
)
and
U
l
(
n
)
as follows:
1
2
·
Pr
U
l
(
n
)
=
x
−
Pr
x
]
=
ma
S
U
l
(
n
)
∈
S
−
Pr
S
]
[
G
(
U
n
)
=
Pr
[
G
(
U
n
)
∈
x
U
l
(
n
)
∈{
G
(
s
):
s
∈{
0
,
1
}
}
n
≥
Pr
≥
2
l
(
n
)
2
n
·
2
−
l
(
n
)
−
1
2
where the last inequality uses
l
(
n
)
≥
n
+
1. Note that for
l
(
n
)
≥
2
n
, the statistical
difference is at least 1
−
2
−
n
.
The foregoing definition is quite permissive regarding the expansion factor
l
:
N→N
.
It asserts only that
l
(
n
)
≥
n
+
1 and
l
(
n
)
≤
poly(
n
). (It also follows that
l
(
n
) is computed
in time polynomial in
n
; e.g., by computing
2
−
(
l
(
n
)
−
n
)
=
1
−
≥
|
G
(1
n
)
|
.) Clearly, a pseudorandom generator
with expansion factor
l
(
n
)
1 is of little value in practice, since it offers no
significant
saving in coin tosses. Fortunately, as shown in the next subsection, even
pseudorandom generators with such a small expansion factor can be used to construct
pseudorandom generators with any polynomial expansion factor. Hence, for every two
expansion factors
l
1
:
=
n
+
that can be computed in poly(
n
) time, there
exists a pseudorandom generator with expansion factor
l
1
if and only if there exists a
pseudorandom generator with expansion factor
l
2
. This statement is proved by using any
pseudorandom generator with expansion factor
l
1
(
n
)
def
N→N
and
l
2
:
N→N
=
n
+
1 to construct, for every
polynomial
p
(
·
), a pseudorandom generator with expansion factor
p
(
n
). Note that a
