4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

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

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.