Cryptography Reference
In-Depth Information
n
(called a
seed
), outputs a string of length
∈{
,
}
(
)
for any input
s
0
1
n
(so that
G
can
}
∗
→{
}
∗
such
:{
,
,
be regarded as a polynomial-time computable function
G
0
1
0
1
}
(
n
)
). Then we say that
G
is a
pseudo-random generator
2
(PRG, for short) of
stretch
(or
expansion factor
)
n
that
G
(
{
0
,
1
}
)
⊆{
0
,
1
if for every PPT distinguisher
D
there exists a negligible function
negl
such that
|
Pr
(
D
(
G
(
s
))
=
1
)
−
Pr
(
D
(
r
)
=
1
)
|≤
negl
(
n
),
}
(
n
)
and every
s
chosen uniformly
for every
r
chosen uniformly at random from
{
0
,
1
n
.
at random from
{
0
,
1
}
Remarks 3.2
1. Recall here that
}
∗
denotes the set of all (finite-length) binary strings, not to
{
0
,
1
Z
2
={
Z
2
.
2. A pseudo-random generator maps random strings of length
n
to pseudo-random
strings of length
be confused with
1
}
, which is the group of units of the ring
(
n
)>
n
and so one might wonder how much longer
(
n
)
should be than
n
. The answer is that this is irrelevant as long as
(
n
)>
n
for,
even if the stretch is
n
→
n
+
1, we can obtain a PRG of stretch
for any
length function
which is polynomial in
n
by just applying
G
recursively to its
own output as many times as necessary. It can be shown (cf., [90, Theorem 3.4],
[109, Theorem 6.23] or [86, Theorem 3.3.3]) that if there exists a polynomial-
time distinguisher able to distinguish its output from random strings of length
(
)
, then the output of
G
would also be distinguishable from random strings of
length
n
n
+
1.
3. The output of a pseudo-random generator cannot be random and, in fact, is far
from random when the stretch is large. When
G
acts on inputs of length
n
,the
number of possible inputs is at most 2
n
and then this is also an upper bound for
the number of strings of length
in the image of
G
. But there are 2
(
n
)
strings
(
n
)
2
n
strings
that are never generated by
G
although, of course, any of them can be chosen at
random according to the uniform distribution. Thus the distribution generated
by
G
cannot be the uniform distribution.
4. The preceding remarks leave open a very important question: Does a pseudo-
random generator actually exist? This problem is open and a necessary condition
for a positive answer is that
, where 2
(
n
)
2
n
, and so there are at least 2
(
n
)
−
of length
(
n
)
>
(otherwise, given a string in the output of
the supposed pseudo-random generator, a short seed giving this string could be
found in polynomial time, thus distinguishing this output from true randomness).
However, even assuming
P
=
NP
, we do not know how to prove that pseudo-
random generators exist (or, equivalently, that one-way functions exist; see the
discussions in [109, Chap. 6] or [86, Chap. 3] as well as Sect.
3.3.3
below).
Let
G
be a pseudo-random generator with stretch
P
=
NP
. The following encryption
scheme is an analogue of the one-time pad which uses short keys:
2
Also called a
cryptographically secure
(or
cryptographically strong
) pseudo-random generator.
