1 Distinguishability and Bit Prediction

Let D be a probability distribution on a finite set Ω. Then D associates a probability P_D(ω) with each each element ω Ω. We will also regard D as a random variable that ranges over Ω and assumes value ω Ω with probability P_D(ω).

Definition: An (S,ℓ)-pseudorandom sequence generator (PRSG) is a function f:S → {0,1}^ℓ. (We generally assume 2^ℓ ≫ |S|.) More properly speaking, a PRSG is a randomness amplifier. Given a random, uniformly distributed seed s S, the PRSG yields the pseudorandom sequence z = f(s). We use S also to denote the uniform distribution on seeds, and we denote the induced probability distribution on pseudorandom sequences by f(S).

The goal of an (S,ℓ)-PRSG is to generate sequences that “look random”, that is, are computationally indistinguishable from sequences drawn from the uniform distribution U on length-ℓ sequences. Informally, a probabilistic algorithm A that always halts “distinguishes” X from Y if its output distribution is “noticeably differently” depending whether its input is drawn at random from X or from Y . Formally, there are many different kinds of distinguishably. In the following definition, the only aspect of A’s behavior that matters is whether or not it outputs “1”. Definition: Let ϵ > 0, let X, Y be distributions on {0,1}^ℓ, and let A be a probabilistic algorithm. Algorithm A naturally induces probability distributions A(X) and A(Y ) on the set of possible outcomes of A. We say that A ϵ-distinguishes X and Y if

and we say X and Y are ϵ-indistinguishable by A if A does not distinguish them.

A natural notion of randomness for PRSG’s is that the next bit should be unpredictable given all of the bits that have been generated so far. Definition: Let ϵ > 0 and 1 ≤ i ≤ ℓ. A probabilistic algorithm N_i is an ϵ-next bit predictor for bit i of f if

where (Z₁,…,Z_ℓ) is distributed according to f(S).

A still stronger notion of randomness for PRSG’s is that each bit i should be unpredictable, even if one is given all of the bits in the sequence except for bit i. Definition: Let ϵ > 0 and 1 ≤ i ≤ ℓ. A probabilistic algorithm B_i is an ϵ-strong bit predictor for bit i of f if

where (Z₁,…,Z_ℓ) is distributed according to f(S).

The close relationship between distinguishability and the two kinds of bit prediction is established in the following theorems.

Proof: Obvious from the definitions. __

Let = (x₁,…,x_ℓ) be a vector. We define ⁱ to be the result of deleting the i^th element of , that is, ⁱ = (x₁,…,x_i-1,x_i+1,…,x_ℓ).

Proof: By definition of A, A() = 1 precisely when B_i(ⁱ) = x_i. Hence, prob[A(f(S)) = 1] ≥ 1∕2 + ϵ. On the other hand, for = U, prob[B_i(ⁱ) = r_i] = 1∕2 since r_i is a uniformly distributed bivalued random variable that is independent of ⁱ. Thus, prob[A(U) = 1] = 1∕2, so A ϵ-distinguishes f(S) and U. __

For the final step in the 3-way equivalence, we have to weaken the error bound.

Proof: Let (Z₁,…,Z_ℓ) = f(S) and (R₁,…,R_ℓ) = U be random variables, and let D_i = (Z₁,…,Z_i,R_i+1,…,R_ℓ). D_i is the distribution on ℓ-bit sequences that results from choosing the first i bits according to f(S) and choosing the last ℓ-i bits uniformly. Clearly D₀ = U and D_ℓ = f(S).

Let p_i = prob[A(D_i) = 1], 0 ≤ i ≤ ℓ. Since A ϵ-distinguishes D_ℓ and D₀, we have |p_ℓ - p₀| ≥ ϵ. Hence, there exists m, 1 ≤ m ≤ ℓ, such that |p_m - p_m-1| ≥ ϵ∕ℓ. We show that the probability that N_m^c correctly predicts bit m for f is 1∕2 + (p_m - p_m-1) if c = 1 and 1∕2 + (p_m-1 - p_m) if c = 0. It will follow that either N_m⁰ or N_m¹ correctly predicts bit m with probability 1∕2 + |p_m - p_m-1|≥ ϵ∕ℓ.

Consider the following experiments. In each, we choose an ℓ-tuple (z₁,…,z_ℓ) according to f(S) and an ℓ-tuple (r₁,…,r_ℓ) according to U.

Let q_j be the probability that experiment E_j succeeds, where j = 0,1,2. Clearly q₂ = (q₀ + q₁)∕2 since r_m = z_m is equally likely as r_m = ¬z_m.

Now, the inputs to A in experiment E₀ are distributed according to D_m, so p_m = q₀. Also, the inputs to A in experiment E₂ are distributed according to D_m-1, so p_m-1 = q₂. Differencing, we get p_m - p_m-1 = q₀ - q₂ = (q₀ - q₁)∕2.

We now analyze the probability that N_m^c correctly predicts bit m of f(S). Assume without loss of generality that A’s output is in {0,1}. A particular run of N_m^c(z₁,…,z_m-1) correctly predicts z_m if

(1)

If r_m = z_m, (1) simplifies to

(2)

and if r_m = ¬z_m, (1) simplifies to

(3)

Let OK_m^c be the event that N_m^c(Z₁,…,Z_m-1) = Z_m, i.e., that N_m^c correctly predicts bit m for f. From (2), it follows that

for in that case the inputs to A are distributed according to experiment E₀. Similarly, from (3), it follows that

for in that case the inputs to A are distributed according to experiment E₁. Since prob[R_m = Z_m] = prob[R_m = ¬Z_m] = 1∕2, we have

{

2 BBS Generator

We now give a PRSG due to Blum, Blum, and Shub for which the problem distinguishing its outputs from the uniform distribution is closely related to the difficulty of determining whether a number with Jacobi symbol 1 is a quadratic residue modulo a certain kind of composite number called a Blum integer. The latter problem is believed to be computationally hard. First some background.

A Blum prime is a prime number p such that p ≡ 3 (mod 4). A Blum integer is a number n = pq, where p and q are Blum primes. Blum primes and Blum integers have the important property that every quadratic residue a has a square root y which is itself a quadratic residue. We call such a y a principal square root of a and denote it by .

Proof: We must show that, modulo p, y is a square root of a and y is a quadratic residue. By the Euler criterion [Theorem 2, handout 15], since a is a quadratic residue modulo p, we have a^(p-1)∕2 ≡ 1 (mod p). Hence, y² ≡ (a^(p+1)∕4)² ≡ aa^(p-1)∕2 ≡ a (mod p), so y is a square root of a modulo p. Applying the Euler criterion now to y, we have

Hence, y is a quadratic residue modulo p. __

Proof: By Lemma 4, a has a principal square root u modulo p and a principal square root v modulo q. Using the Chinese remainder theorem, we can find x that solves the equations

for each of the four choices of signs in the two equations, yielding 4 square roots of a modulo n. It is easily shown that the x that results from the +,+ choice is a quadratic residue modulo n, and the others are not. __

From Theorem 4, it follows that the mapping bb² mod n is a bijection from the set of quadratic residues modulo n onto itself. (A bijection is a function that is 1–1 and onto.)

Definition: The Blum-Blum-Shub generator BBS is defined by a Blum integer n = pq and an integer ℓ. It is a (Z* _n,ℓ)-PRSG defined as follows: Given a seed s₀ Z*_n, we define a sequence s₁,s₂,s₃,…,s_ℓ, where s_i = s_i-1² mod n for i = 1,…,ℓ. The ℓ-bit output sequence is b₁,b₂,b₃,…,b_ℓ , where b_i = s_i mod 2.

Note that any s_m uniquely determines the entire sequence s₁,…,s_ℓ and corresponding output bits. Clearly, s_m determines s_m+1 since s_m+1 = s_m² mod n. But likewise, s_m determines s_m-1 since s_m-1 = , the principal square root of s_m modulo n, which is unique by Theorem 5.

3 Security of BBS

Proof: From A, one easily constructs an algorithm  that reverses its input and then applies A.  ϵ-distinguishes the reverse of BBS(Z*_n) from U. By Theorem 3, there is an ϵ′-next bit predictor N_m for bit ℓ - m + 1 of BBS reversed. Thus, N_m(b_ℓ,b_ℓ-1,…,b_m+1) correctly outputs b_m with probability at least 1∕2 + ϵ′, where (b₁,…,b_ℓ) is the (unreversed) output from BBS(Z*_n).

We now describe algorithm Q(x), assuming x Z*_n and = 1. Using x as a seed, compute (b₁,…,b_ℓ) = BBS(x) and let b = N_m(b_ℓ-m,b_ℓ-m-1,…,b₁). Output “quadratic residue” if b = x mod 2 and “non-residue” otherwise.

To see that this works, observe first that N_m(b_ℓ-m,b_ℓ-m-1,…,b₁) correctly predicts b₀ with probability at least 1∕2 + ϵ′, where b₀ = ( mod n) mod 2. This is because we could in principle let s_m+1 = x² mod n and then work backwards defining s_m = mod n, s_m-1 = mod n, …, s₀ = mod n. It follows that b₀,…,b_ℓ-m are the last ℓ - m + 1 bits of BBS(s₀), and b₀ is the bit predicted by N_m.

Now, x and -x are clearly square roots of s_m+1. We show that they both have Jacobi symbol 1. Since = ⋅ = 1, then either = = 1 or = = -1. But because p and q are Blum primes, -1 is a quadratic non-residue modulo both p and q, so = = -1. It follows that = 1. Hence, x = ±, so exactly one of x and -x is a quadratic residue.

Since n is odd, x mod n and -x mod n have opposite parity. Hence, x is a quadratic residue iff x and have the same parity. But N_m outputs mod 2 with probability 1∕2 + ϵ′, so it follows that Q correctly determines the quadratic residuosity of its argument with probability 1∕2 + ϵ′. __