Pseudo-Random Number Generator From ANY One-Way Function

We construct a pseudo-random number generator from ANY one-way function. Previous results show how to construct pseudo-random number generators from one-way functions that have special properties (Blum and Micali, Yao, Levin, Goldreich, Krawczyk and Luby). We use techniques borrowed from the theory of slightly-random sources (Santha and Vazirani, Vazirani and Vazirani, Vazirani, Chor and Goldreich) and from the theory of universal hash functions (Carter and Wegman). We also introduce a weaker kind of one-way function, that we call an informationally one-way function. For an informationally one-way function f, given y = f(x) for a randomly chosen x, it is hard to generate uniformly a random preimage of y. We show that the existence of an informationally one-way function yields a one-way function in the usual sense, and hence a pseudo-random number generator. These results can be combined to show that the following are equivalent: (1) private key encryption; (2) bit commitment; (3) pseudo-random number generators; (4) one-way functions; (5) informationally one-way functions.

ICSI Technical Report TR-89-002

Technical Report