Previous slide Next slide Back to the first slide View text version


This problem has a very interesting history. Blum and Micali show how to create pseudorandom generators based on the hardness of discrete logarithm. Yao generalizes their algorithm to create a generator based on any one-way permutation. Levin shows a technical one-way property of functions that he can use to create secure pseudorandom generators. Goldreich, Krawczyk and Luby show how to convert a ``regular'' one-way function to a pseudorandom generator. Impagliazzo, Levin and Luby then showed Theorem. Finally, Hastad extended the techniques of Impagliazzo, Levin and Luby to show how to construct pseudo-random functions from any uniformly one-way function.

The proof of Theorem uses a new idea of computational entropy. In other words, they use a one-way function to create a distribution that may not have large real entropy or randomness but does have large entropy in a computational sense. They then use this pseudoentropy distribution to create the pseudorandom generator. Their techniques make important use of a result of Goldreich and Levin that shows how to get a ``hard-core'' bit out of any one-way function.