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 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.