Cryptography Reference
In-Depth Information
indistinguishable from (and hence practically the same as) a true random bit se-
quence. Combining the two conditions yields a PRBG that is secure and can be used
for cryptographic purposes. Referring to the fundamental results of Blum, Micali,
and Yao (mentioned earlier), a PRBG is cryptographically secure if it passes the
next-bit test (and hence all polynomial-time statistical tests) possibly under some
intractability assumption.
If one has a one-way function
f
with hard-core predicate
B
, then a crypto-
graphically secure PRBG
G
with seed
s
0
can be constructed as follows:
G
(
s
0
)=
B
(
s
0
)
,B
(
f
(
s
0
))
,B
(
f
2
(
s
0
))
,...,B
(
f
l
(
|s
0
|
)
−
1
(
s
0
))
Talking in terms of an FSM-based PRBG, the state register is initialized with
s
0
, the next-state function
f
is the one-way function, and the output function
g
com-
putes the hard-core predicate
B
. This idea is employed by many cryptographically
secure PRBGs. The three most important examples—the Blum-Micali, RSA, and
BBS PRBGs—are overviewed and briefly discussed next.
12.2.1
Blum-Micali PRBG
The Blum-Micali PRBG [9] as specified in Algorithm 12.2 employs the fact that the
discrete exponentiation function is a (conjectured) one-way function (see Section
7.2.1) and that the MSB is a hard-core predicate of it. The PRBG takes as input
a large prime
p
and a generator
g
of
Z
p
. It is initialized by randomly selecting a
Z
p
. The PRBG then generates an output bit
b
i
by computing
x
i
=
g
x
i
−
1
(mod
p
) and setting
b
i
=
msb
(
x
i
) for
i
seed
x
0
=
s
0
from
1. A potentially infinite bit
sequence (
b
i
)
i≥
1
can be generated along this way. It is the output of the Blum-Micali
PRBG.
≥
Algorithm 12.2
The Blum-Micali PRBG.
(
p, g
)
x
0
∈
R
Z
p
for
i
=1to
∞
do
x
i
← g
x
i
−
1
(mod
p
)
b
i
← msb
(
x
i
)
output
b
i
(
b
i
)
i≥
1
The security of the Blum-Micali PRBG is based on the DLA (see Definition
7.4). This means that anybody who is able to compute discrete logarithms can also
break the security of the Blum-Micali PRBG.
