Cryptography: Theory and Practice:Pseudo-random Number Generation

Cryptography: Theory and Practice
by Douglas Stinson
CRC Press, CRC Press LLC
ISBN: 0849385210 Pub Date: 03/17/95

Table of Contents

The relevance to PRBGs is as follows. Consider the sequence of bits produced by the PRBG. There are possible sequences, and if the bits were chosen independently at random, each of these sequences would occur with equal probability . Thus a truly random sequence corresponds to an equiprobable distribution on the set of all bit-strings of length . Suppose we denote this probability distribution by p₀.

Now, consider sequences produced by the PRBG. Suppose a k-bit seed is chosen at random, and then the PRBG is used to obtain a bit-string of length . Then we obtain a probability distribution on the set of all bit-strings of length , which we denote by p₁. (For the purposes of illustration, suppose we make the simplifying assumption that no two seeds give rise to the same sequence of bits. Then, of the possible sequences, 2_k sequences each occur with probability 1/2_k, and the remaining sequences never occur. So, in this case, the probability distribution p₁ is very non-uniform.)

Even though the two probability distributions p₀ and p₁ may be quite different, it is still conceivable that they might be ε-distinguishable only for small values of ε. This is our objective in constructing PRBGs.

Example 12.3

Suppose that a PRBG only produces sequences in which exactly bits have the value 0 and bits have the value 1. Define the function A by

In this case, the algorithm A is deterministic. It is not hard to see that

and

It can be shown that

Hence, for any fixed value of ε < 1, p₀ and p₁ are ε-distinguishable if is sufficiently large.

12.2.1 Next Bit Predictors

Another useful concept in studying PRBGs is that of a next bit predictor, which works as follows. Let f be a -PRBG. Suppose we have a probabilistic algorithm B_i, which takes as input the first i-1 bits produced by f (given an unknown seed), say z₁, …, z_i-1, and attempts to predict the next bit z_i. The value i can be any value such that . We say that B_i is an ε-next bit predictor if B_i can predict the ith bit of a pseudo-random sequence with probability at least 1/2 + ε, where ε > 0.

We can give a more precise formulation of this concept in terms of probability distributions, as follows. We have already defined the probability distribution p₁ on induced by the PRBG f. We can also look at the probability distributions induced by f on any of the pseudo-random output bits (or indeed on any subset of these output bits). So, for , we will can think of the ith pseudo-random output bit as a random variable that we will denote by z_i.

In view of these definitions, we have the following characterization of a next bit predictor.

THEOREM 12.1

Let f be a -PRBG. Then the probabilistic algorithm B_i is an ε-next bit predictor for f if and only if

PROOF The probability of correctly predicting the ith bit is computed by summing over all possible (i - 1)-tuples (z₁, … , z_i-1) the product of the probability that the (i - 1)-tuple, (z₁,…, z_i-1) is produced by the PRBG and the probability that the ith bit is predicted correctly given the (i - 1)-tuple, (z₁, … , z_i-1).

The reason for the expression 1/2 + ε in this definition is that any predicting algorithm can predict the next bit of a random sequence with probability 1/2. If a sequence is not random, then it may be possible to predict the next bit with higher probability. (Note that it is unnecessary to consider algorithms that predict the next bit with probability less than 1/2, because in this case an algorithm that replaces every prediction z by 1 - z will predict the next bit with probability greater than 1/2.)

We illustrate these ideas by producing a next-bit predictor for the Linear Congruential Generator of Example 12.1.

Example 12.1 (Cont.)

For any i such that 1 ≤ i ≤ 9, Define B_i(z) = 1 - z. That is, B_i predicts that a 0 is most likely to be followed by a 1, and vice versa. It is not hard to compute from Table 12.1 that each of these predictors B_i is a -next bit predictor (i.e., they predict the next bit correctly with probability 20/31).

We can use a next bit predictor to construct a distinguishing algorithm A, as shown in Figure 12.3. The input to algorithm A is a sequence of bits, , and A calls the algorithm B_i as a subroutine.

Figure 12.3 Constructing a distinguisher from a next bit predictor

THEOREM 12.2

Suppose B_i is an ε-next bit predictor for the -PRBG f. Let p₁ be the probability distribution induced on by f, and let p₀ be the uniform probability distribution on . Then A, as described in Figure 12.3, is an ε-distinguisher of p₁ and p₀.

PROOF First, observe that

Also, the output of A is independent of the values of . Thus we can compute as follows:

Table of Contents