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.
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 above construction, and repeated times we get the mapping
Theorem 3 (Blum-Micali) Let be a permutation, and suppose is -hard core for and that are computable with complexity .
Then as defined in (1) is -pseudorandom.
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.