Modern Cryptography: Theory and Practice

The Blum-Blum-Shub Generator is presented in Figure 12.6. The generator works quite simply. Given a seed s₀ ∈ QR(n), we compute the sequence by successive squaring modulo n, and then reduce each s_i modulo 2 to obtain z_i. It follows that

.

We now give an example of the BBS Generator.

Example 12.4

Suppose n = 192649 = 383 × 503 and s₀ = 101355² mod n = 20749. The first 20 bits produced by the BBS Generator are computed as shown in Table 12.3. Hence the bit-string resulting from this seed is

11001110000100111010.

Here is a feature of the BBS Generator that is useful when we look at its security. Since n = pq where p ≡ q ≡ 3 mod 4, it follows that for any quadratic residue x, there is a unique square root of x that is also a quadratic residue. This square root is called the principal square root of x. It follows the mapping mod n used to define the BBS Generator is a permutation on QR(n), the set of quadratic residues modulo n.

12.3.1 Security of the BBS Generator

In this section, we look at the security of the BBS Generator in detail. We begin by supposing that the pseudo-random bits produced by the BBS Generator are ε-distinguishable from random bits and then see where that leads us. Throughout this section, n = pq, where p and q are primes such that p ≡ q ≡ 3 mod 4, and the factorization n = pq is unknown.

We have already discussed the idea of a next bit predictor. In this section we consider a similar concept that we call a previous bit predictor. A previous bit predictor for a -BBS Generator will take as input pseudo-random bits produced by the generator (as determined by an unknown random seed s₀ ∈ QR(n)), and attempt to predict the value z₀ = s₀ mod 2. A previous bit predictor can be a probabilistic algorithm, and we say that a previous bit predictor B₀ is an ε-previous bit predictor if its probability of correctly guessing z₀ is at least 1/2 + ε, where this probability is computed over all possible seeds s₀.

We state the following theorem, which is similar to Theorem 12.3, without proof.

THEOREM 12.4

Suppose A, is an ε-distinguisher of p₁ and p₀, where p₁ is the probability distribution induced on by the -BBS Generator, f, and p₀ is the uniform probability distribution on . Then there exists an -previous bit predictor B₀ for f.

We now show how to use an -previous bit predictor, B₀, to construct a probabilistic algorithm that distinguishes quadratic residues modulo n from pseudo-squares modulo n with probability 1/2 + ε. This algorithm A, presented in Figure 12.7, uses B₀ as a subroutine, or oracle.

THEOREM 12.5

Suppose B₀ is an ε-previous bit predictor for the -BBS Generator f. Then the algorithm A, as described in Figure 12.7, determines quadratic residuosity correctly with probability at least 1/2 + ε, where this probability is computed over all possible inputs .

PROOF  Since n = pq and p ≡ q ≡ 3 mod 4, it follows that so . Hence, if then the principal square root s₀ = x² is x if x ∈ QR(n); and -x if . But

so it follows that algorithm A gives the correct answer if and only if B₀ correctly predicts z. The result then follows immediately.

Figure 12.7  Constructing a quadratic residue distinguisher from a previous bit predictor

Theorem 12.5 shows how we can distinguish pseudo-squares from quadratic residues with probability at least 1/2 + ε. We now show that this leads to a Monte Carlo algorithm that gives the correct answer with probability at least 1/2 + ε. In other words, for any , the Monte Carlo algorithm gives the correct answer with probabilty at least 1/2 + ε. Note that this algorithm is an unbiased algorithm (it may give an incorrect answer for any input) in contrast to the Monte Carlo algorithms that we studied in Section 4.5 which were all biased algorithms.

The Monte Carlo algorithm A₁ is presented in Figure 12.8. It calls the previous algorithm A as a subroutine.

Copyright © CRC Press LLC