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.

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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