# Pseudorandom Generators from One-Way Functions: A Simple Construction for Any Hardness

## Thomas Holenstein

```
```In a seminal paper, Hastad, Impagliazzo, Levin, and Luby showed
that pseudorandom generators exist if and only if one-way functions
exist. The construction they propose to obtain a pseudorandom
generator from an n-bit one-way function uses O(n^8) random
bits in the input (which is the most important complexity measure of
such a construction). In this work we study how much this can be
reduced if the one-way function satisfies a stronger security
requirement. For example, we show how to obtain a pseudorandom
generator which satisfies a standard notion of security using only
O(n^4 log^2(n)) bits of randomness if a one-way function with
exponential security is given, i.e., a one-way function for which no
polynomial time algorithm has probability higher than 2^(-cn) in
inverting for some constant c.
Using the uniform variant of Impagliazzo's hard-core lemma given in
[Hol05] our constructions and proofs are self-contained
within this paper, and as a special case of our main theorem, we
give the first explicit description of the most efficient
construction from [HILL99].