Cryptography Reference
In-Depth Information
Algorithm 12.4
The BBS PRBG.
(
n
)
x
0
∈
R
Z
n
for
i
=1to
∞
do
x
i
← x
i−
1
(mod
n
)
b
i
←
lsb
(
x
i
)
output
b
i
(
b
i
)
i≥
1
Alternatively speaking, the BBS PRBG takes as input a large Blum integer
n
and generates the following binary output sequence (using a randomly chosen seed
x
0
):
G
(
x
0
)=
lsb
(
x
0
)
,lsb
(
x
0
2
mod
n
)
,...,lsb
(
x
0
2
l
(
|
x
0
|
)
−
1
mod
n
)
From a practical viewpoint, the BBS PRBG is the cryptographically secure
PRBG of choice used in many applications. There are basically two reasons:
•
First, the BBS PRBG is efficient. It requires only one modular squaring for the
generation of an output bit. Furthermore, the efficiency of the PRBG can be
improved by extracting the
j
=
c
log log
n
least significant bits of
x
i
(instead
of only the LSB).
•
Second, the BBS PRBG has the practically relevant property that
x
i
can be
computed directly for
i
≥
1 if one knows the prime factors
p
and
q
of
n
:
x
i
=
x
(2
i
)mod((
p−
1)(
q−
1))
0
In either case (and similar to the RSA PRBG), the security of the BBS PRBG
is based on the IFA (see Definition 7.10 on page 178).
12.3
FINAL REMARKS
In this chapter, we introduced the notion of a PRBG and elaborated on the require-
ments for a PRBG to be cryptographically secure. In short, a cryptographically se-
cure PRBG is an efficient deterministic algorithm that is able to stretch a binary
input sequence into a longer output sequence, and for which no PPT algorithm can
