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.

  • 2
    $\begingroup$ Try using the definitions. $\endgroup$ – Yuval Filmus Jun 17 '20 at 22:16
  • $\begingroup$ "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? $\endgroup$ – Pedro Costa Jun 18 '20 at 9:30
  • $\begingroup$ These are not formal definitions. Try using the formal definitions. $\endgroup$ – Yuval Filmus Jun 18 '20 at 9:32
  • $\begingroup$ 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$? $\endgroup$ – Pedro Costa Jun 18 '20 at 10:30
  • $\begingroup$ Have you seen any proofs using these definitions? $\endgroup$ – Yuval Filmus Jun 18 '20 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.