# 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 2k/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 x0 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.