Cryptography Reference
In-Depth Information
the pseudo-random one-time pad is computationally secure in the sense mentioned,
while a second reduction is provided by Theorem 3.10 which shows that BBS is
indeed a PRG under the factoring assumption. Combining both reductions, we have:
•
The pseudo-random one-time pad based on the Blum-Blum-Shub PRG is com-
putationally secure, in the sense of Remark 3.3, under the factoring assumption
.
Remarks 3.5
BBS is the preferred PRG for cryptographic applications for the fol-
lowing reasons:
1. Its security reduction relies on a well-understood problem: the factorization
problem.
2. BBS is relatively efficient as it requires only one modular squaring per output
bit.
3. In practice, the BBS PRG can be implemented even more efficiently if one
knows the prime factors
p
,
q
of
n
, for then the
x
i
in Definition 3.19 can be
x
2
i
mod
φ(
n
)
0
computed directly as
x
i
=
mod
n
, where
φ(
n
)
=
(
p
−
1
)(
q
−
1
)
.
In this situation, the exponents 2
i
mod
φ(
n
)
may be pre-computed and their
computation requires
O
(
len
(
i
))
multiplications modulo
φ(
n
)
. Thus
x
i
may be
computed from
x
0
and
φ(
n
)
, without previous knowledge of
x
i
−
1
, in time
3
2
O
(
max
(
len
(
n
)
,
len
(
i
)
len
(
n
)
))
, while using the definition directly this com-
2
putation takes time
O
. Another advantage of this method is that if
BBS is used to generate a long key (for example, for the pseudo-random one-
time pad), then a ciphertext can be decrypted from any starting point without
forming the bit string from the beginning.
(
i
len
(
n
)
)
3.3.3.1 Concluding Remarks on PRGs and One-Way Functions
We have seen in this section that a key ingredient of private-key cryptography, namely,
pseudo-random generators, is obtained from the hypothesis that one-way functions
exist. It can also be shown that the existence of one-way functions suffices to guaran-
tee the existence of pseudo-random permutations, another key ingredient of private-
key cryptography for, as we shall see, they are the theoretical models on which block
ciphers are built. We will also see that one-way functions and, specifically, trapdoor
one-way functions are also crucial for public-key cryptography so that it can be said
that the concept of one-way function (and the related concept of one-way permuta-
tion) is the most important cryptographic primitive. We refer to Chap. 6 of [109] for
a detailed and accessible discussion of these questions.
3.4 PRGs and Related Constructions in Maple
In this section we review, from a cryptographic perspective, Maple's algorithms for
the generation of pseudo-random numbers. Since not all of them satisfy Definition
3.4, we will not call them PRGs and we will often generically refer to them as
'pseudo-random algorithms' instead.
