YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

CPSC 461b: Foundations of Cryptography Notes 12 (rev. 1)
Professor M. J. Fischer February 19, 2009

Lecture Notes 12

29 Pseudorandom Generators

Definition: An ensemble X = {Xn}n∈ℕ is pseudorandom if X, U are indistinguishable in polynomial time, where U = {Un}n∈ℕ is the uniform ensemble.

Thus, X is pseudorandom if it “looks” the same to all probabilistic polynomial time algorithms.

Definition: A pseudorandom generator is a deterministic polynomial time function G that satisfies two properties:

  1. G maps strings of length n to strings of length ℓ(n) > n. ℓ(n) is called the expansion factor.
  2. {G(Un)}n∈ℕ is pseudorandom.

We remark that if G is a pseudorandom generator, then G(Un) is not statistically close to Uℓ(n). To see this, let RG = {G(x)∣x ∈{0,1}n} be the range of G. Clearly, |RG|≤ 2n, and for all y ⁄∈ RG, Pr[G(Un) = y] = 0. On the other hand, for the uniform ensemble, Pr[Uℓ(n) = y] = -1ℓ 2. Hence, the statistical difference

∑ Δ(ℓ(n)) = 1- |P r[G(Un ) = α] - Pr[Uℓ(n) = α]| 2 α∈{0,1}ℓ(n) ∑ ≥ 1- |P r[G(Un ) = α ]- Pr[Uℓ(n) = α]| 2 α∈RG 1 ∑ 1 = -- |0 - -ℓ| 2 α∈RG 2 ℓ n = 1-⋅ 2--ℓ2- ≥ 1, 2 2 4
is not negligible, so G(Un) and Uℓ(n) are not statistically close.

We now describe how to build a pseudorandom number generator G with polynomial expansion factor starting from a generator G1 with expansion factor ℓ(n) = n + 1.

Fix a polynomial p(n). For s ∈{0,1}n, write the length-(n + 1) string G1(s) as σs′, where |σ| = 1 and |s′| = n. On input s, iteratively define the sequences s0,s1,s2,…,sp(n) and σ1,σ2,…,σp(n) as follows:

s0 = s σisi = G1(si-1), for i = 0,1,2,...,p(n) - 1.

The output of G(s) is the sequence σ1σ2…σp(n). G(s) is easily computed in polynomial time by a simple iterative program that calls G1 a total of p(n) times.

Theorem 1 If G1 is pseudorandom, then so is G.

Proof is by a hybrid argument. We let hybrid Hnk consist of k uniform random bits followed by the first p(n) - k bits of G(s0), which we write as G(so):[1,p(n) - k]. In symbols,

Hk = U ⋅G(U ):[1,p(n)- k]. n k n

Clearly, Hn0 = G(Un) and Hnp(n) = Up(n).

Suppose D distinguishes G(Un) from Up(n) with absolute probability difference δ(n). Then for some k, D distinguishes Hnk from Hnk+1 with absolute probability difference ≥ δ(n)∕p(n).

We now describe an algorithm D′ that attempts to distinguish G1(Un) from Un+1. On length-(n + 1) input α, D′ does the following:

1. Write α = τ ⋅ α′, where |τ| = 1 and |α′| = n.

2. Choose index k uniformly from {0,1,…,p(n) - 1}.

3. Choose a uniformly distributed string β of length k.

4. Construct y = β ⋅ τ ⋅ G(α′):[1,p(n) - k - 1].

5, Compute and output D(y).

If α is uniformly distributed, then τ and α′ are both uniformly distributed, so y = Hnk+1. On the other hand, if α = G1(s0), where s0 is uniformly distributed, then τ = σ1 and α′ = s1, so y = Hnk. This is because

G(s0):[1,p(n) - k] = τ ⋅G (s1):[1,p(n )- k - 1]

Hence, D′ distinguishes G1(Un) from Un+1 with absolute probability difference ≥ δ(n)∕p(n).

We omit the remaining details of showing how this leads to a contradiction of the assumption that G is not pseudorandom.

30 Unpredictability

Our formal definition of pseudorandomness is based on the indistinguishability of an entire polynomial-length generated sequence from a uniformly distributed random sequence. However, the traditional notion of a pseudorandom generator is based on repeated experiments. The output bits x1,x2,… are assumed to be generated one at a time. The generator is called pseudorandom if each xi “appears” to result from an independent and uniformly distributed random event such as the flip of a fair coin.

The notion of “appears” is can be captured in terms of unpredictability. We say that xi+1 is unpredictable if no polynomial time algorithm that attempts to guess it is correct with more than a tiny advantage over chance, even given all of the prior bits x1,…,xi.

More formally, a predictor is a p.p.t. algorithm A that is allowed to read the input sequence x a bit at a time in order. After reading bit i, the algorithm can choose to output a guess b and halt, or it can continue. In any case, it must halt and emit a guess after reading the next-to-last bit of x. Let k be the last bit read by A. Then A is correct if k < |x| and b = xk+1. In addition to the input x, which A is allowed to read only a bit at a time, A is also given an input 1n, where n = |x|. This way, A can determine the length of x without having to read it all.

Notation: The textbook uses the notation nextA(x) to denote the next bit of x following the last bit that A read. The intent is that the event [A(1|Xn|,Xn) = nextA(Xn)] should mean that a string x is chosen according to the distribution Xn, A is run on inputs 1n and x, A reads the first k bits of x for some k and outputs b, and b = xk+1, the “next” bit of x. That is, the event is that A correctly predicts some bit of a randomly chosen x from distribution Xn.

A better notation would make k explicit. For example, we could pretend that A outputs a pair (k,b) with the meaning that k is the index of the last bit of x that A read, and b is A’s prediction for xk+1. We could then define nextA(x) = {(k,xk+1)∣k ∈ [0,n - 1]}. Now, A correctly predicts the next bit if A(1|x|,x) = (k,b) and (k,b) ∈ nextA(x).

Definition: An ensemble {Xn}n∈ℕ is called unpredictable in polynomial time if for every p.p.t. A, every positive polynomial p(⋅), and all sufficiently large n,

|x| 1 1 Pr[A (1 ,x) ∈ nextA(x)] < 2 + p(n).

Theorem 2 An ensemble X is pseudorandom if and only if it is unpredictable in polynomial time.

Proof:  
(⇒) The theorem in the forward direction is straightforward. We sketch the general ideas and leave the details to the reader.

If there were a predictor A for X, then a distinguisher D is easily built. Namely, D(x) outputs 1 iff A(1|x|,x) correctly predicts the next bit. If x comes from X, D(x) will output 1 with probability at least 1 2 + 1 p(n), but if x comes from U, then clearly D(x) will output 1 with probability exactly 1 2. Hence, D successfully distinguishes X from U.
(⇐) The theorem in the reverse direction is proved by another hybrid argument. We sketch a few of the main ideas. Assume X is both unpredictable but not pseudorandom. Then there is a distinguisher D such that

|Pr[D (X ) = 1]- P r[D (U ) = 1]| ≥ -1-- n n p(n)

for infinitely many n. We may without loss of generality drop the absolute value brackets and assume that

1 Pr[D (Xn ) = 1]- P r[D (Un) = 1] ≥ p(n-)

for infinitely many n. The reasoning is that either Pr[D(Xn) = 1] ≥ Pr[D(Un) = 1] for infinitely many n, or Pr[D(Xn) = 1] ≤ Pr[D(Un) = 1] for infinitely many n. If the latter, then Pr[¯D(Xn) = 1] ≥ Pr[D¯(Un) = 1] for the algorithm D¯ that is identical to D except that it complements the output.

We build a next-bit predictor A. Let hybrid Hnk consist of the first k bits from Xn followed by the last n - k bits from Un. Then Hnn = Xn and Hn0 = Un. The predictor A(1|x|,x) guesses a number k ∈ [0,|x|- 1], reads only the first k bits of x, and constructs the string y = x1,…,xk,uk+1,…,un, where the uj’s are uniformly distributed random bits. It then runs D(y). If D(y) = 1, then A predicts bit k + 1 to be uk+1. Otherwise, A predicts bit k + 1 to be ¬uk+1 (the complement of uk+1).

We omit the non-trivial analysis needed to show that algorithm A has a sufficient advantage as a next-bit predictor to contradict the assumption that X is unpredictable. __

31 Pseudorandom Generators and One-Way Functions

We now show that the existence of pseudorandom generators implies the existence of one-way functions.

Theorem 3 Let G be a pseudorandom generator with expansion factor ℓ(n) = 2n. Define the function f(x,y) = G(x) for all |x| = |y|. Then f is a strongly one-way function.

Proof: Suppose f is not strongly one-way. Let A be an inverter for f(U2n) with success probability at least -1-- p(n) for infinitely many n. We construct a distinguisher D that distinguishes G(Un) from U2n on those same n.

D(α) uses A to attempt to find β such that f(β) = α. If A succeeds, then D outputs 1; otherwise D outputs 0. Since f(U2n) = G(Un), then

1 P r[D (G(Un )) = 1] = P r[f(A(f(U2n))) = f(U2n)] ≥ p-(n-).
(1)

On the other hand,

P r[D (U ) = 1] = P r[f(A (U )) = U ] ≤-1-. 2n 2n 2n 2n
(2)

This is because f(x,y) depends only on x, so the range of f on pairs of length-n inputs has size ≤ 2n. Since f(A(U2n)) is in the range of f, the probability that U2n is in the range, much less actually equal to f(A(U2n)), is at most 2-n. Subtracting 2 from 1 gives

--1- -1- --1-- Pr[D (G(Un)) = 1]- P r[D (U2n) = 1] ≥ p(n) - 2n ≥ 2p(n).
(3)

Thus, D distinguishes G(Un) from U2n for infinitely many n, contradicting the assumption that G is a pseudorandom generator. __