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

On the other hand, any predictor B_i will predict the ith bit of a truly random sequence with probability 1/2. Then, it is not difficult to see that E_A (p₀) = 1/2. Hence |E_A (p₀) - E_A (p₁)| ≥ ε, as desired.

One of the main results in the theory of pseudo-random bit generators, due to Yao, is that a next bit predictor is a universal test. That is, a PRBG is “secure” if and only if there does not exist an ε-next bit predictor except for very small values of ε. Theorem 12.2 proves the implication in one direction. To prove the converse, we need to show how the existence of a distinguisher implies the existence of a next bit predictor. This is done in Theorem 12.3.

THEOREM 12.3

Suppose A, is an ε-distinguisher of p₁ and p₀, where p₁ is the probability distribution induced on by the -PRBG f, and p₀ is the uniform probability distribution on . Then for some i, , there exists an -next bit predictor B_i for f.

PROOF For , define q_i to be a probability distribution on where the first i bits are generated using f, and the remaining bits are generated at random. Thus q₀ = p₀ and . We are given that

By the triangle inequality, we have that

Hence, it follows that there is at least one value , such that

Without loss of generality, we will assume that

We are going to construct an ith bit predictor (for this specified value of i). The predicting algorithm is probabilistic in nature and is presented in Figure 12.4. Here is the idea behind this construction. The predicting algorithm in fact produces an -tuple according to the probability distribution q_i - 1, given that z₁,…,z_i-1are generated by the PRBG. If A answers “0,” then it thinks that the -tuple was most likely generated according to the probability distribution q_i. Now q_i-1 and q_i differ only in that the ith bit is generated at random in q_i-1, whereas it is generated according to the PRBG in q_i. Hence, when A answers “0,” it thinks that the ith bit, z_i, is what would be produced by the PRBG. Hence, in this case we take z_i as our prediction of the ith bit. If A answers “1,” it thinks that z_i is random, so we take 1 - z_i as our prediction of the ith bit.

We need to compute the probability that the ith bit is predicted correctly. Observe that if A answers “0,” then the prediction is correct with probability

Figure 12.4 Constructing a next bit predictor from a distinguisher

where p₁ is the probability distribution induced by the PRBG. If A answers “1,” then the prediction is correct with probability

For brevity, we denote . In our computation, we will make use of the fact that

This can be proved easily as follows:

Now we can perform our main computation:

which was what we wanted to prove.

12.3 The Blum-Blum-Shub Generator

In this section we describe one of the most popular PRBGs, due to Blum, Blum, and Shub. First, we review some results on Jacobi symbols from Section 4.5 and other number-theoretic facts from other parts of Chapter 4.

Suppose p and q are two distinct primes, and let n = pq. Recall that the Jacobi symbol

Denote the quadratic residues modulo n by QR (n). That is,

Recall that x is a quadratic residue modulo n if and only if

Define

Thus

An element is called a pseudo-square modulo n.

The Blum-Blum-Shub Generator, as well as some other cryptographic systems, is based on the Quadratic Residues problem defined in Figure 12.5. (In Chapter 4, we defined the Quadratic Residues problem modulo a prime and showed that it is easy to solve; here we have a composite modulus.) Observe that the Quadratic Residues problem requires us to distinguish quadratic residues modulo n from pseudo-squares modulo n. This can be no more difficult than factoring n. For if the factorization n = pq can be computed, then it is a simple matter to compute , say. Given that , it follows that x is a quadratic residue if and only if .

Figure 12.5 Quadratic Residues

Figure 12.6 Blum-Blum-Shub Generator

There does not appear to be any way to solve the Quadratic Residues problem efficiently if the factorization of n is not known. So this problem appears to be intractible if it is infeasible to factor n.

Table of Contents