Scribed by Siu-On Chan
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 be a -one way permutation computable in time . Then the predicate is hard core for the permutation .
A way to look at this result is the following: suppose is one way and computable in time. Then is a hard-core predicate for the permutation .
From now on, we shall assume that we have a one-way permutation and a predicate that is hard core for .
This already gives us a pseudorandom generator with one-bit expansion.
Theorem 2 (Yao) Let be a permutation, and suppose is -hard core for . Then the mapping
is -pseudorandom generator mapping bits into bits.
Note that is required to be a permutation rather than just a function. If 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 is given by Goldreich-Levin, the mapping would be
Proof: Suppose the mapping is not -pseudorandom. There is an algorithm of complexity such that
where we have used the fact that since is permutation, would be a uniformly random element in when is such.
We will first remove the absolute sign in (1). The new inequality holds for either or (i.e. the complement of ), and they both have complexity at most .
Now define an algorithm as follows.
On input , pick a random bit . If , then output , otherwise output .
Algorithm has complexity at most . We claim that
so is not -hard core.
To make explicit the dependence of on , we will denote by the fact that picks as its random bit.
To prove the claim, we expand
Note that no matter what is. The above probability thus becomes
The second term is just . Now we add to and subtract from (2) the quantity , getting
The expression in the bracket is , and by our assumption on , the whole expression is more than , as claimed.
The main idea of the proof is to convert something that distinguishes (i.e. ) to something that outputs (i.e. ). helps us distinguish good answers and bad answers.
We will amplify the expansion of the generator by the following idea: from an -bit input, we run the generator to obtain pseudorandom bits. We output one of those bits and feed the other back into the generator, and so on. Specialized to the above construction, and repeated times the mapping becomes
This corresponds to the following diagram where all output bits lie at the bottom.
Theorem 3 (Blum-Micali) Let be a permutation, and suppose is -hard core for and that are computable with complexity .
Then as defined in (3) is -pseudorandom.
Proof: Suppose is not -pseudorandom. Then there is an algorithm of complexity at most such that
We will then use the hybrid argument. We will define a sequence of distributions , the first is ‘s output, the last is uniformly random bits, and every two adjacent ones differ only in one invocation of .
More specifically, define to be the distribution where we intercept the output of the first copies of ‘s, replace them with random bits, and run the rest of as usual (see the above figure in which blue lines represent intercepted outputs). Then is just the distribution of the output of , and is the uniform distribution, as desired. Now
So there is an such that
In both and , the first bits are random. We now define a new algorithm that takes as input and has output distribution or in two special cases: if are drawn from , then has output distribution ; if are drawn from (random bit),, then has output distribution . In other words, if are , should output
If are (random bit),, should output
This suggests that on input should pick random bits and output .
and is not -hard core.
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 be a pseudorandom generator computable in time , let be the first bits of the output of , and let be the last bits of the output of .
Prove that is a pseudorandom generator.