YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE
CPSC 467b: Cryptography and Computer Security | Handout #14 | |
Professor M. J. Fischer | April 6, 2010 | |
Pseudorandom Sequence Generation
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_{1},…,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_{1},…,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.
Theorem 1 Suppose ϵ > 0 and N_{i} is an ϵ-next bit predictor for bit i of f. Then algorithm B_{i} is an ϵ-strong bit predictor for bit i of f, where algorithm B_{i}(z_{1},…,z_{i-1},z_{i+1},…,z_{ℓ}) simply ignores its last ℓ - i inputs and computes N_{i}(z_{1},…,z_{i-1}).
Proof: Obvious from the definitions. __
Let = (x_{1},…,x_{ℓ}) be a vector. We define ^{i} to be the result of deleting the i^{th} element of , that is, ^{i} = (x_{1},…,x_{i-1},x_{i+1},…,x_{ℓ}).
Theorem 2 Suppose ϵ > 0 and B_{i} is an ϵ-strong bit predictor for bit i of f. Then algorithm A ϵ-distinguishes f(S) and U, where algorithm A on input outputs 1 if B_{i}(^{i}) = x_{i} and outputs 0 otherwise.
Proof: By definition of A, A() = 1 precisely when B_{i}(^{i}) = x_{i}. Hence, P[A(f(S)) = 1] ≥ 1∕2 + ϵ. On the other hand, for = U, P[B_{i}(^{i}) = r_{i}] = 1∕2 since r_{i} is a uniformly distributed bivalued random variable that is independent of ^{i}. Thus, P[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.
Theorem 3 Suppose ϵ > 0 and algorithm A ϵ-distinguishes f(S) and U. For each 1 ≤ i ≤ ℓ and c {0,1}, define algorithm N_{i}^{c}(z_{1},…,z_{i-1}) as follows:
1. | Flip coins to generate ℓ - i + 1 random bits r_{i},…,r_{ℓ}. |
2. | Let v = |
3. | Output v ⊕ r_{i} ⊕ c. |
Then there exist m and c for which algorithm N_{m}^{c} is an ϵ∕ℓ-next bit predictor for bit m of f.
Proof: Let (Z_{1},…,Z_{ℓ}) = f(S) and (R_{1},…,R_{ℓ}) = U be random variables, and let D_{i} = (Z_{1},…,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_{0} = U and D_{ℓ} = f(S).
Let p_{i} = P[A(D_{i}) = 1], 0 ≤ i ≤ ℓ. Since A ϵ-distinguishes D_{ℓ} and D_{0}, we have |p_{ℓ} - p_{0}| ≥ ϵ. 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}^{0} or N_{m}^{1} correctly predicts bit m with probability 1∕2 + |p_{m} - p_{m-1}|≥ ϵ∕ℓ.
Consider the following experiments. In each, we choose an ℓ-tuple (z_{1},…,z_{ℓ}) according to f(S) and an ℓ-tuple (r_{1},…,r_{ℓ}) according to U.
Let q_{j} be the probability that experiment E_{j} succeeds, where j = 0,1,2. Clearly q_{2} = (q_{0} + q_{1})∕2 since r_{m} = z_{m} is equally likely as r_{m} = ¬z_{m}.
Now, the inputs to A in experiment E_{0} are distributed according to D_{m}, so p_{m} = q_{0}. Also, the inputs to A in experiment E_{2} are distributed according to D_{m-1}, so p_{m-1} = q_{2}. Differencing, we get p_{m} - p_{m-1} = q_{0} - q_{2} = (q_{0} - q_{1})∕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_{1},…,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_{1},…,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_{0}. Similarly, from (3), it follows that
for in that case the inputs to A are distributed according to experiment E_{1}. Since P[R_{m} = Z_{m}] = P[R_{m} = ¬Z_{m}] = 1∕2, we have
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 .
Lemma 4 Let p be a Blum prime, and let a be a quadratic residue modulo p. Then y = a^{(p+1)∕4} mod p is a principal square root of a modulo p.
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^{2} ≡ (a^{(p+1)∕4})^{2} ≡ 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. __
Theorem 5 Let n = pq be a Blum integer, and let a be a quadratic residue modulo n. Then a has four square roots modulo n, exactly one of which is a principal square root.
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^{2} 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_{0} Z*_{n}, we define a sequence s_{1},s_{2},s_{3},…,s_{ℓ}, where s_{i} = s_{i-1}^{2} mod n for i = 1,…,ℓ. The ℓ-bit output sequence is b_{1},b_{2},b_{3},…,b_{ℓ} , where b_{i} = s_{i} mod 2.
Note that any s_{m} uniquely determines the entire sequence s_{1},…,s_{ℓ} and corresponding output bits. Clearly, s_{m} determines s_{m+1} since s_{m+1} = s_{m}^{2} 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.
Theorem 6 Suppose there is a probabilistic algorithm A that ϵ-distinguishes BBS(Z*_{n}) from U. Then there is a probabilistic algorithm Q(x) that correctly determines with probability at least ϵ′ = ϵ∕ℓ whether or not an input x Z*_{n} with Jacobi symbol = 1 is a quadratic residue modulo n.
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_{1},…,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_{1},…,b_{ℓ}) = BBS(x) and let b = N_{m}(b_{ℓ-m},b_{ℓ-m-1},…,b_{1}). 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_{1}) correctly predicts b_{0} with probability at least 1∕2 + ϵ′, where b_{0} = ( mod n) mod 2. This is because we could in principle let s_{m+1} = x^{2} mod n and then work backwards defining s_{m} = mod n, s_{m-1} = mod n, …, s_{0} = mod n. It follows that b_{0},…,b_{ℓ-m} are the last ℓ - m + 1 bits of BBS(s_{0}), and b_{0} 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 + ϵ′. __