# Is a one-way function pseudorandom?

For one-way function $f$ I understand that $g(x)=0^{n}\mathbin\|f(x)$ is a one- way function with respect to $2n$, where there is $n$ bits of $0$ in the beginning and the output of $f$ in the second half.

However, is this also a pseudorandom generator? My first guess was that, because it is easy to find a number that could be an output from $g$, that it isn't pseudorandom. My understanding of pseudorandom generator isn't quite clear, but it seems based on the definition of computational indistinguishability that the distribution of $g$ indistinguishable from uniform, so does that make it a PRG?

Not all one-way functions are pseudorandom. We'll show that with the help of the fact in the first part of the question (which we accept as granted, as does the question):

If $f$ is a $n$-bit one-way function, then $g(x)=0^{n}\mathbin\|f(x)$ is a $2n$-bit one-way function.

We'll use an intuitive definition of a pseudorandom function: a function which can't be distinguished (in polynomial time) from a random function (with the same input and output sets). That sidesteps (as the question does) the more precise formalism of pseudorandom function family.

Consider this test for a $m$-bit function $h$: compute $h(x)$ for $x$ the all-zero input, and output $\mathtt{false}$ if all the left $\left\lfloor m/2\right\rfloor$ bits of the result are zero; otherwise output $\mathtt{true}$.

That test runs in polynomial time w.r.t. $n$, assuming $h$ does. When that test is applied to a function $g$ constructed as in our fact, it outputs $\mathtt{false}$ with probability $1$. When that test is applied to a random $2n$-bit function $h$, it outputs $\mathtt{false}$ with probability $2^{-n}$, since each of the $n$ bit(s) tested is uniformly random. For $n>0$, it holds $1>2^{-n}$, therefore that test distinguishes (a) any function $g$ constructed as in our fact from (b) a random function with the same input and output sets as $g$. Therefore, for $n>0$, any function $g$ constructed as in our fact is not a random function.

We now only need to hypothesize the existence of a $n$-bit one way function $f$ to have exhibited a counterexample $g$ to the assertion that all one-way functions are pseudorandom, thus proving the first sentence of this answer.

The question errs when it states

because it is easy to find a number that could be an output from $g$, that isn't pseudorandom.

Problem with that line of thought: it holds including for a pseudo-random function $f$ that "it is easy to find a number that could be an output from $f$"; in particular, the all-zero bitstring $0^{2n}$ is such "number".

We can try and make that quantitative: the all-zero bitstring $0^{2n}$ is much more likely to occur for $g$ (probability $2^{-n}$ with some extra hypothesis) than it is for a random function $f$ with the same output set (probability $2^{-2n}$).

But it's not enough to remark that it is easy to find a number more likely to be an output from $g$ than it is to be an output for random function $f$. Problem with that alternate line of thought: as $n$ grows, it becomes exponentially unlikely that a certain number will be the output of $g$ or $f$, thus we can't build a polynomial-time distinguisher from the existence of a single such number.

Note, per comment: this answer assimilates a pseudorandom generator to a pseudorandom function (as does the question), by fixing the output width of the PRG to the width $n$ of the pseudorandom function, and using the PRG's key/seed as the input of the pseudorandom function.

• The question is about pseudorandom generators, not pseudorandom functions. – fkraiem Sep 15 '18 at 7:48