# If g is a PRG and f is a OWF, is G'(x) = f(g(x)) a PRG?

Just like the title states.

If I have a pseudo-random generator $$g\colon \Sigma^n \rightarrow \Sigma^{2n}$$ and a one-way function $$f$$, is $$g'(x)=f(g(x))$$ a pseudo-random generator? And why?

My instinct tells me it is, but I can't really explain why.

• Try using the definitions. – Yuval Filmus Jun 17 '20 at 22:16
• "A Pseudorandom generator (PRG) is an efficient and deterministic function, which returns a longer pseudorandom output sequence based on the received shorter input: $G:{0,1}^s \rightarrow {0,1}^n$, where $n >> s$." "A one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input." Does it have to do with the fact that $f$ is not guaranteed to "strech" the input string? – Pedro Costa Jun 18 '20 at 9:30
• These are not formal definitions. Try using the formal definitions. – Yuval Filmus Jun 18 '20 at 9:32
• I'm looking at the wikipedia formal definition (my professor's slides are really lacking) and I can't seem to figure it out. Is it because it is possible that $f$ won't "cheat" a distinguisher, since the statistical distance between the distributions $A(G(U_{\ell }))$ and $A(U_{n})$ can be become greater than $\epsilon$? – Pedro Costa Jun 18 '20 at 10:30
• Have you seen any proofs using these definitions? – Yuval Filmus Jun 18 '20 at 12:45