# 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 '17 at 14:29
• @tylo I updated the question, could you look again? – Napoleon Nov 27 '17 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. – Maeher Nov 28 '17 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 – Napoleon Nov 28 '17 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. – Napoleon Nov 29 '17 at 14:36
• $1/p(n) - 2^{n}/(2^{n+1}*p(n)) = 1/p(n)$ so G isn't a PRG – sosolo Nov 29 '17 at 15:09