Prove that pseudorandom generator is a one way function

Suppose the following PRG $G : \{0,1\}^n \rightarrow \{0,1\}^{n +l}$, I want to prove that $G$ is one way function (and not building one), for:

1. $l = \omega (\log n)$
2. $l = 1$

For $l = \log n$, suppose that $G$ isn't OWF, so there's an inverter $A$ which succeeds w.p. $\geq 1/p(n)$, trying to build a distinguisher $B$ from inverter $A$ to $G$, I can do as follows:

$B(y)$ assigns 1 to each input successfully inverted. So $\Pr[B(y) = 1 : y = f(x) = G(x)] \geq 1/p(n)$, and for random input $\Pr[B(U_{n + \log n})] \geq 2^{n}/2^{\log n + n}$. All in all, the distinguisher succeeds w.p.

$$|\Pr[B(y) = 1 : y = f(x) = G(x)] - \Pr[B(U_{n + \log n})]| \geq 1/n - 1/p(n) \geq 1/2n$$

But for $l=1$, I get a bound of $1/4$ ($1/2 -1/p(n) \geq 1/4$)... It doesn't feel correct, but does (?) follow the definition of distinguisher for PRGs.

What am I missing?

• From the question, it's completely unclear what you are actually doing, and then where the problem is. But maybe this question and answer is helpful to you. However, the properties of PRFs, PRGs and OWFs are to some degree related but not the same. For a correct proof the details matter.
– tylo
Nov 27, 2017 at 14:29
• @tylo I updated the question, could you look again? Nov 27, 2017 at 15:17
• What exactly is your question? Why 1/4 is sufficient advantage for a PRF distinguisher? Your proof itself - though missing a lot of details - would appear to be on the right track. Nov 28, 2017 at 1:12
• I want to prove that $G$ is OWF. 1/4 is enough, because its PRG should be computional indistinguishble for any negligible function, and 1/4 is greater for any negligeble function Nov 28, 2017 at 7:48

$$l = \log n: \Pr[B(Un+\log n)]≥2^n/2^{n+\log n} \cdot 1/p(n)$$ Since even if the input of $B$ is from the image of $G$, the probability to invert it is $1/p(n)$. So you need to correct this case and it will help you with $l = 1$.
• Firat of all, shouldn't your bound be $\leq$ (cause otherwise you can't bound $|\Pr[B(G(U_n)) = 1] - \Pr[B(U_{n + \log n})]|$)? Second, if I follow your way, for $l = \log n$ we get bound of $1/2p(n)\log n$, and for $l = 1$ we've get a bound of $\geq 2^n/2^{n+1}/p(n) = 1/2p(n)$. Am I correct? And finally, I stiil don't understand what's wrong with my previous way. Nov 29, 2017 at 14:36
• $1/p(n) - 2^{n}/(2^{n+1}*p(n)) = 1/p(n)$ so G isn't a PRG Nov 29, 2017 at 15:09