# Background and Classification

- 5.1 Definition A
*random bit generator*is a device or algorithm which outputs a sequence of statistically independent and unbiased binary digits. - 5.2 Remark (
*random bits*vs.*random numbers*) A random bit generator can be used to generate (uniformly distributed) random numbers. For example, a random integer in the interval [0,*n]*can be obtained by generating a random bit sequence of length [lg nj + 1, and converting it to an integer; if the resulting integer exceeds n, one option is to discard it and generate a new random bit sequence.

§5.2 outlines some physical sources of random bits that are used in practice. Ideally, secrets required in cryptographic algorithms and protocols should be generated with a (true) random bit generator. However, the generation of random bits is an inefficient procedure in most practical environments. Moreover, it may be impractical to securely store and transmit a large number of random bits if these are required in applications such as the one-time pad (§6.1.1). In such situations, the problem can be ameliorated by substituting a random bit generator with a pseudorandom bit generator.

5.3 Definition A *pseudorandom bit generator* (PRBG) is a deterministic^{[1]} algorithm which, given a truly random binary sequence of length *k,* outputs a binary sequence of length *l* » *к *which “appears” to be random. The input to the PRBG is called the *seed,* while the output of the PRBG is called a *pseudorandom bit sequence.*

The output of a PRBG is *not* random; in fact, the number of possible output sequences is at most a small fraction, namely *2 ^{k}/2^{[1]},* of all possible binary sequences of length

*l.*The intent is to take a small truly random sequence and expand it to a sequence of much larger length, in such a way that an adversary cannot efficiently distinguish between output sequences of the PRBG and truly random sequences of length

*l.*§5.3 discusses ad-hoc techniques for pseudorandom bit generation. In order to gain confidence that such generators are secure, they should be subjected to a variety of statistical tests designed to detect the specific characteristics expected of random sequences. A collection of such tests is given in §5.4. As the following example demonstrates, passing these statistical tests is a

*necessary*but not

*sufficient*condition for a generator to be secure.

5.4 Example (*linear congruential generators*) A *linear congruential generator* produces a pseudorandom sequence of numbers **x, ***x%, ***хз,***...* according to the linear recurrence

integers *a, b,* and *m* are *parameters* which characterize the generator, while *x _{0}* is the (secret)

*seed.*While such generators are commonly used for simulation purposes and probabilistic algorithms, and pass the statistical tests of §5.4, they are

*predictable*and hence entirely insecure for cryptographic purposes: given a partial output sequence, the remainder of the sequence can be reconstructed even if the parameters

*a, b,*and

*m*are unknown. □

A minimum security requirement for a pseudorandom bit generator is that the length *k* of the random seed should be sufficiently large so that a search over elements (the total number of possible seeds) is infeasible for the adversary. Two general requirements are that the output sequences of a PRBG should be statistically indistinguishable from truly random sequences, and the output bits should be unpredictable to an adversary with limited computational resources; these requirements are captured in Definitions 5.5 and 5.6.

- 5.5 Definition A pseudorandom bit generator is said to pass all
*polynomial-time*^{[3]}*statistical tests*if no polynomial-time algorithm can correctly distinguish between an output sequence of the generator and a truly random sequence of the same length with probability significantly greater that A. - 5.6 Definition A pseudorandom bit generator is said to pass the
*next-bit test*if there is no polynomial-time algorithm which, on input of the first*l*bits of an output sequence*s,*can predict the*(l*+ l)^{st}bit of s with probability significantly greater than A.

Although Definition 5.5 appears to impose a more stringent security requirement on pseudorandom bit generators than Definition 5.6 does, the next result asserts that they are, in fact, equivalent.

- 5.7 Fact (
*universality> of the next-bit test*) A pseudorandom bit generator passes the next-bit test if and only if it passes all polynomial-time statistical tests. - 5.8 Definition A PRBG that passes the next-bit test (possibly under some plausible but unproved mathematical assumption such as the intractability of factoring integers) is called a
*cryptographically secure pseudorandom bit generator*(CSPRBG). - 5.9 Remark
*(asymptotic nature of Definitions*5.5,*5.6, and 5.8*) Each of the three definitions above are given in complexity-theoretic terms and are asymptotic in nature because the notion of “polynomial-time” is meaningful for asymptotically large inputs only; the resulting notions of security are relative in the same sense. To be more precise in Definitions 5.5,5.6, 5.8, and Fact 5.7, a pseudorandom bit generator is actually*a family*of such PRBGs. Thus the theoretical security results for a family of PRBGs are only an indirect indication about the security of individual members.

Two cryptographically secure pseudorandom bit generators are presented in §5.5.

- [1] Deterministic here means that given the same initial seed, the generator will always produce the same outputsequence.
- [2] Deterministic here means that given the same initial seed, the generator will always produce the same outputsequence.
- [3] The running tune of the test is bounded by a polynomial in the length / of the output sequence.