Katz/Lindell Problem 7.6

Question

Let $f$ be a length-preserving one-way function, and let $\text{hc}$ be a hard-core predicate of $f$. Define $G$ as $G(x)=f(x)\|\text{hc}(x)$. Is $G$ necessarily a pseudorandom generator?

The answer is yes if $f$ is a pseudorandom permutation according to theorem 7.6 in the book. I am fairly certain that the answer is no if $f$ is no longer bijective. Intuitively, the first part of the string $G(x)$ is no longer uniformly distributed if we choose a uniformly random $x$, so $G$ should generally not be pseudorandom. However, I think it may depend on how far $f$ strays from bijectivity, as demonstrated by the following two extreme cases:

1. If $f$ were constant (taking a value $y_0$), then an obvious distinguisher would be the done that outputs $1$ if the first part of the string $G(x)$ is $y_0$. This has advantage $1-2^{-n+1}$, which is not negligible. The issue, of course, is that $f$ is clearly not a one-way function.
2. If $f$ misses precisely one point of its codomain, then there is some $y_0$ which is hit exactly twice. Then the distinguisher from the above example has advantage $2\cdot 2^{-n+1}-2^{-n+1} = 2^{-n+1}$, which is negligible. I can't think of a better distinguisher either.

Answer 1

Let $g(x)$ be a length-preserving one-way function. Then $f(b||x)=1||g(x)$ (where $b$ is one bit of input) is a length-preserving one-way function and $\text{hc}(b||x)=b$ is a hard-core predicate for $f$. But $G(b||x)=f(b||x)\|\text{hc}(b||x)$ is not a pseudorandom generator.

So the answer to the problem is no.

edit: My original answer did not prove that the counterexample $f$ actually had a hard-core predicate.