Pseudo-random generation from one-way functions

Abstract

We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when x is chosen randomly: (1) from ƒ(x) it is hard to recover an x1 with ƒ(x1) = ƒ(x) by a small circuit, or; (2) ƒ has small degeneracy and from ƒ(x) it is hard to recover x by a fast algorithm. From one-way functions of type (1) or (2) we show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Previous results show how to construct pseudo-random generators from one-way functions that have special properties ([Blum, Micali 82], [Yao 82], [Levin 85], [Goldreich, Krawczyk, Luby 88]).