Cryptography Reference
In-Depth Information
=
≡
≡
Definition 3.19
Let
n
pq
, where
p
and
q
are primes such that
p
q
(
)
: N → N
3
mod 4
.Let
be a polynomial-time computable function such that
(
t
)>
t
for every
t
∈ N
. Then the
Blum-Blum-Shub
PRG of stretch
is the func-
}
∗
→{
}
∗
defined as follows.
tion
G
:{
0
,
1
0
,
1
s
2
mod
n
}
∗
, with len
•
Select
s
∈[
1
,
n
−
1
]
at random and, for
x
0
=
∈{
0
,
1
(
x
0
)
=
t
t
) and
i
(i.e.,
x
0
∈{
0
,
1
}
=
1
,...,(
t
)
, compute:
x
0
x
1
=
mod
n
,
b
1
=
x
1
mod 2
,
x
1
x
2
=
mod
n
,
b
2
=
x
2
mod 2
,
.
.
(3.1)
x
i
−
1
x
i
=
mod
n
,
b
i
=
x
i
mod 2
,
.
.
x
2
(
x
)
=
mod
n
,
b
)
=
x
mod 2
.
(
t
(
t
(
t
)
t
)
−
1
•
(
x
0
)
=
b
1
b
2
...
Define
G
b
(
t
)
.
From the preceding results we now obtain:
Theorem 3.10
Under the factoring assumption, Blum-Blum-Shub is a pseudo-
random generator.
Proof
This is a consequence of Theorems 3.5, 3.8 and 3.9.
Remark 3.10
All existence proofs of PRGs are, like this one, conditional. Condi-
tional proofs of this type are usually based on
reductions
which show that a problem
is hard under the assumption that some other problem (which, ideally, should be
well-understood) is also hard. Here, we see that Blum-Blum-Shub is indeed a PRG
if the factorization problem (for Blum integers) is hard but, of course, the latter
has not been proved. However, we feel that the factorization problem, which has a
longer history than PRGs, is better understood than the latter and, because of this,
the reduction is useful.
Exercise 3.14
Give an informal argument showing that if pseudo-randomgenerators
exist then one-way functions exist. (Hint: If
G
is a PRG with stretch 2
n
, show that
G
itself is one-way by showing that a PPT algorithm
able to invert
G
with non-
negligible probability can be used as a subroutine for a distinguisher
D
that, given a
string
s
A
2
n
outputs 1 if
G
∈{
0
,
1
}
(A(
s
))
=
s
and 0 otherwise).
We already gave an informal proof of the fact that the pseudo-random one-time
pad introduced in Definition 3.5 is “computationally secure”—in the intuitive sense
mentioned in Remark 3.5, which is made more precise in Sect.
3.5.2
, where the
formal definitions of security are given—assuming that the underlying generator
G
is indeed a PRG. Now we can refine this by specifying the BBS PRG as the one to
be used to generate the long keys. The informal argument relies on two reductions:
the one made in Remark 3.5 shows that if we use a PRG to generate long keys, then
