# Why can't we construct a PRG from a one-way function and hc, but only one-way permutation

From Katz & Lindell's book, theorem 7.19:

Let f be a one way permutation with hard-core predicate hc.

Then the algorithm $$G(s)=f(s)||hc(s)$$ is a PRG with expansion factor $$\ell(n)=n+1$$.

But what about if we use a one-way function? I know that there could be $$f(x)=f(x^{'})$$ when $$x\neq x^{'}$$, we lost some entropy here, but what breaks the theorem actually?

## 1 Answer

The proof of Theorem 7.19 explicitly uses that $f(r)$ for a uniformly random bitstring $r$ is distributed like $r$ when $f$ is a permutation*. I don't have the energy to reprint the proof here to show exactly how the distribution of $f(r)$ is used, but it should be clear that it can be useful to know this about $f(r)$ when arguing that $G$ is a PRG.

If you want a counterexample when $f$ is not a permutation you can see this answer.

*This is the part of the proof that says

using the fact that $f$ is a permutation for the second equality

for those who have access to the book.