Cryptography Reference
In-Depth Information
Other practically relevant PRBGs are, for example, specified in FIPS PUB 186
[5]. Although such ad hoc methods to generate pseudorandom bit sequences have not
proven to be secure in a cryptographical sense, they appear sufficiently secure for
most (cryptographic) applications. Unfortunately, only a few publications elaborate
on the exact cryptographical strength of such a PRBG (e.g., [6]). For example, some
PRBGs (including the ANSI X9.17 PRBG) have the property that once the internal
state has been compromised, an adversary is forever after able to predict the output
bit sequence of the PRBG. From a theoretical point of view, this is a minor concern
and does not disturb the overall security of the PRBG (because one assumes that the
adversary is not able to read out the internal state of the PRBG). From a practical
point of view, however, this is a major concern and may require reseeding the PRBG
periodically.
One branch of research tries to find PRBG constructions that are resistant
against all known attacks. The resulting PRBGs are relevant and called
practically
strong
. Note, however, that a practically strong PRBG is not necessarily secure in
a cryptographical sense and that it is only assumed to be secure against a specific
set of attacks that is known at some point in time. On the positive side, practically
strong PRBGs are usually very efficient and can be implemented entirely in software.
Possible constructions for practically strong PRBGs are given in [7] and [8]. For the
purpose of this topic, we don't further address practically strong PRBGs. Instead,
we elaborate on PRBGs that are secure in a cryptographically strong sense; they are
called cryptographically secure.
2
12.2
CRYPTOGRAPHICALLY SECURE PRBG
From a theoretical point of view, there are many possibilities to formally define
what “secure in a cryptographically strong sense” or “cryptographically secure”
means with respect to PRBGs. Historically, the first possibility was formalized
by Manuel Blum and Silvio Micali in the early 1980s [9]. They called a PRBG
cryptographically secure if an adversary cannot guess the next bit in a sequence from
the prefix of the sequence better than guessing at random, and they also proposed
the first method for designing such a cryptographically secure PRBG based on the
DLA (see Definition 7.4). Leonore Blum, Manuel Blum, and Michael Shub proposed
another PRBG, called the
BBS PRBG
or
squaring generator
, which is simpler to
implement and provably secure assuming that the QRP (see Definition 3.32) is hard
[10]. Later it was shown that the assumption that the QRP is hard can be replaced
by the weaker assumption that the IFP is hard [11]. A related PRBG is obtained by
using the RSA function. All three PRBGs are addressed later.
2
Cryptographically secure PRBGs are sometimes also called
cryptographically strong
.
