Scribed by Siu-On Chan

Summary

Today we complete the proof that it is possible to construct a pseudorandom generator from a one-way permutation.

1. Pseudorandom Generators from One-Way Permutations

Last time we proved the Goldreich-Levin theorem.

Theorem 1 (Goldreich and Levin) Let ${f: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n}$ be a ${(t,\epsilon)}$-one way permutation computable in time ${r\leq t}$. Then the predicate ${x,r \mapsto \langle x,r \rangle}$ is ${(\Omega( t \cdot \epsilon^2 \cdot n^{-O(1)} , 3\epsilon)}$ hard core for the permutation ${x,r \mapsto f(x),r}$.

A way to look at this result is the following: suppose ${f}$ is ${(2^{\Omega(n)},2^{-\Omega(n)})}$ one way and computable in ${n^{O(1)}}$ time. Then ${\langle x,r \rangle}$ is a ${(2^{\Omega(n)},2^{-\Omega(n)})}$ hard-core predicate for the permutation ${x,r \rightarrow f(x),r}$.

From now on, we shall assume that we have a one-way permutation ${f: \{ 0,1 \}^n \rightarrow \{ 0,1 \}^n}$ and a predicate ${P:\{ 0,1 \}^n \rightarrow \{ 0,1 \}}$ that is ${(t,\epsilon)}$ hard core for ${f}$.

This already gives us a pseudorandom generator with one-bit expansion.

Theorem 2 (Yao) Let ${f:\{ 0,1 \}^n \rightarrow \{ 0,1 \}^n}$ be a permutation, and suppose ${P:\{ 0,1 \}^n \rightarrow \{ 0,1 \}}$ is ${(t,\epsilon)}$-hard core for ${f}$. Then the mapping

$\displaystyle x \mapsto P(x),f(x)$

is ${(t-O(1), \epsilon)}$-pseudorandom generator mapping ${n}$ bits into ${n+1}$ bits.

Note that ${f}$ is required to be a permutation rather than just a function. If ${f}$ is merely a function, it may always begin with 0 and the overall mapping would not be pseudorandom.

For the special case where the predicate ${P}$ is given by Goldreich-Levin, the mapping would be

$\displaystyle x \mapsto \langle x,r \rangle,f(x),r$

Proof: Suppose the mapping is not ${(t-2,\epsilon)}$-pseudorandom. There is an algorithm ${D}$ of complexity ${\leq t-2}$ such that

$\displaystyle \left|\mathop{\mathbb P}_{x\sim\{0,1\}^n} [D(P(x)f(x))=1] - \mathop{\mathop{\mathbb P}_{b\sim\{0,1\}}}_{x\sim\{0,1\}^n} [D(bf(x))=1]\right| > \epsilon \ \ \ \ \ (1)$

where we have used the fact that since ${f}$ is permutation, ${f(x)}$ would be a uniformly random element in ${\{0,1\}^n}$ when ${x}$ is such.

We will first remove the absolute sign in (1). The new inequality holds for either ${D}$ or ${1-D}$ (i.e. the complement of ${D}$), and they both have complexity at most ${t-1}$.

Now define an algorithm ${A}$ as follows.

On input ${y=f(x)}$, pick a random bit ${r\sim\{0,1\}}$. If ${D(r,y)=1}$, then output ${r}$, otherwise output ${1-r}$.

Algorithm ${A}$ has complexity at most ${t}$. We claim that

$\displaystyle \mathop{\mathbb P}_{x\sim\{0,1\}^n} [A(f(x))=P(x)]> \frac12+\epsilon$

so ${P(\cdot)}$ is not ${(t,\epsilon)}$-hard core.

To make explicit the dependence of ${A}$ on ${r}$, we will denote by ${A_r(f(x))}$ the fact that ${A}$ picks ${r}$ as its random bit.

To prove the claim, we expand

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}_{x,r} [A_r(f(x))=P(x)] &= & \mathop{\mathbb P}_{x,r} [A_r(f(x))=P(x)\mid r=P(x)]\mathop{\mathbb P}[r=P(x)] + \\ && \mathop{\mathbb P}_{x,r} [A_r(f(x))=P(x)\mid r\neq P(x)]\mathop{\mathbb P}[r\neq P(x)] \\ \end{array}$

Note that ${\mathop{\mathbb P}[r=P(x)]=\mathop{\mathbb P}[r\neq P(x)]=1/2}$ no matter what ${P(x)}$ is. The above probability thus becomes

$\displaystyle \frac12 \mathop{\mathbb P}_{x,r} [D(rf(x))=1\mid r=P(x)] + \frac12 \mathop{\mathbb P}_{x,r} [D(rf(x))=0\mid r\neq P(x) ] \ \ \ \ \ (2)$

The second term is just ${\frac12 - \frac12 \mathop{\mathbb P}_{x,r} [D(rf(x))=1\mid r\neq P(x) ]}$. Now we add to and subtract from (2) the quantity ${\frac12 \mathop{\mathbb P}_{x,r} [D(rf(x))=1\mid r=P(x) ]}$, getting

$\displaystyle \frac12 + \mathop{\mathbb P}_{x,r} [D(rf(x))=1\mid r=P(x)] -$

$\displaystyle \left(\frac12 \mathop{\mathbb P}[D(rf(x))=1\mid r=P(x)] + \right.$

$\displaystyle \left.\frac12 \mathop{\mathbb P}[D(rf(x))=1\mid r\neq P(x)]\right)$

The expression in the bracket is ${\mathop{\mathbb P}[D(rf(x))=1]}$, and by our assumption on ${D}$, the whole expression is more than ${\frac12 + \epsilon}$, as claimed. $\Box$

The main idea of the proof is to convert something that distinguishes (i.e. ${D}$) to something that outputs (i.e. ${A}$). ${D}$ helps us distinguish good answers and bad answers.

We will amplify the expansion of the generator by the following idea: from an ${n}$-bit input, we run the generator to obtain ${n+1}$ pseudorandom bits. We output one of those ${n+1}$ bits and feed the other ${n}$ back into the generator, and so on. Specialized to the above construction, and repeated ${k}$ times the mapping becomes

$\displaystyle G_k (x) := P(x), P(f(x)), P(f(f(x)), \ldots, P(f^{(k-1)} (x), f^{(k)} (x) \ \ \ \ \ (3)$

This corresponds to the following diagram where all output bits lie at the bottom.

Theorem 3 (Blum-Micali) Let ${f:\{ 0,1 \}^n \rightarrow \{ 0,1 \}^n}$ be a permutation, and suppose ${P:\{ 0,1 \}^n \rightarrow \{ 0,1 \}}$ is ${(t,\epsilon)}$-hard core for ${f}$ and that ${f,P}$ are computable with complexity ${r}$.

Then ${G_k : \{ 0,1 \}^n \rightarrow \{ 0,1 \}^{n+k}}$ as defined in (3) is ${(t-O(rk), \epsilon k)}$-pseudorandom.

Proof: Suppose ${G_k}$ is not ${(t-O(rk),\epsilon k)}$-pseudorandom. Then there is an algorithm ${D}$ of complexity at most ${t-O(rk)}$ such that

$\displaystyle \left| \mathop{\mathbb P}_{x\sim\{0,1\}^n} [D(G_k(x))=1]-\mathop{\mathbb P}_{z\sim\{0,1\}^{n+k}} [D(z)=1] \right| > \epsilon k$

We will then use the hybrid argument. We will define a sequence of distributions ${H_0,\dots,H_k}$, the first is ${G_k}$‘s output, the last is uniformly random bits, and every two adjacent ones differ only in one invocation of ${G}$.

More specifically, define ${H_i}$ to be the distribution where we intercept the output of the first ${i}$ copies of ${G}$‘s, replace them with random bits, and run the rest of ${G_k}$ as usual (see the above figure in which blue lines represent intercepted outputs). Then ${H_0}$ is just the distribution of the output of ${G_k}$, and ${H_k}$ is the uniform distribution, as desired. Now

$\displaystyle \begin{array}{rcl} \epsilon k &< & \left|\mathop{\mathbb P}_{z\sim H_0} [D(z)=1]-\mathop{\mathbb P}_{z\sim H_k} [D(z)=1]\right| \\ &= & \left|\sum_{i=0}^{k-1}\left(\mathop{\mathbb P}_{z\sim H_i} [D(z)=1]-\mathop{\mathbb P}_{z\sim H_{i+1}} [D(z)=1] \right) \right| \end{array}$

So there is an ${i}$ such that

$\displaystyle \left|\mathop{\mathbb P}_{z\sim H_i} [D(z)=1]-\mathop{\mathbb P}_{z\sim H_{i+1}}[D(z)=1]\right| > \epsilon$

In both ${H_i}$ and ${H_{i+1}}$, the first ${i}$ bits ${r_1,\dots,r_i}$ are random. We now define a new algorithm ${D'}$ that takes as input ${b,y}$ and has output distribution ${H_i}$ or ${H_{i+1}}$ in two special cases: if ${b,y}$ are drawn from ${P(x),f(x)}$, then ${D'}$ has output distribution ${H_i}$; if ${b,y}$ are drawn from (random bit),${f(x)}$, then ${D'}$ has output distribution ${H_{i+1}}$. In other words, if ${b,y}$ are ${P(x),f(x)}$, ${D'}$ should output

$\displaystyle r_1,\dots,r_i,P(x),P(f(x)),\dots,P(f^{(k-i-1)}(x)),f^{(k-i)}(x)$

If ${b,y}$ are (random bit),${f(x)}$, ${D'}$ should output

$\displaystyle r_1,\dots,r_i,r_{i+1},P(f(x)),\dots,P(f^{(k-i-1)}(x)),f^{(k-i)}(x)$

This suggests that ${D'}$ on input ${b,y}$ should pick random bits ${r_1,\dots,r_i}$ and output ${r_1,\dots,r_i,b,P(y),\dots,P(f^{(k-i-2)}(y)),f^{(k-i-1)}(y)}$.

We have

$\displaystyle \begin{array}{rcl} & & \left| \mathop{\mathbb P}_{x\sim\{0,1\}^n}[D'(P(x)f(x))=1]-\mathop{\mathbb P}_{z\sim\{0,1\}^{n+1}}[D'(z)=1] \right| \\ &= & \left| \mathop{\mathbb P}_{x\sim H_i} [D'(x)=1] - \mathop{\mathbb P}_{x\sim H_{i+1}} [D'(x)=1] \right| \\ &> & \epsilon \end{array}$

and ${P(\cdot)}$ is not ${(t,\epsilon)}$-hard core. $\Box$

Thinking about the following problem is a good preparation for the proof the main result of the next lecture.

Exercise 1 (Tree Composition of Generators) Let ${G:\{ 0,1 \}^n \rightarrow \{ 0,1 \}^{2n}}$ be a ${(t,\epsilon)}$ pseudorandom generator computable in time ${r}$, let ${G_0(x)}$ be the first ${n}$ bits of the output of ${G(x)}$, and let ${G_1(x)}$ be the last ${n}$ bits of the output of ${G(x)}$.

Define ${G' : \{ 0,1 \}^n \rightarrow \{ 0,1 \}^{4n}}$ as

$\displaystyle G' (x) = G(G_0(x)), G( G_1 (x))$

Prove that ${G'}$ is a ${(t-O(r),3\epsilon)}$ pseudorandom generator.