Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG.

Being $\alpha$ a constant, is it possible to build a secure PRG $G' : \left\{0,1\right\}^{\alpha\lambda} \rightarrow \left\{0,1\right\}^{\alpha(\lambda+l)}$ using $G_1$ and $G_2$?

My intuition is that it can't be done, but I don't know how to prove it.

  • $\begingroup$ In order to show that something can’t be done, you need to explain the rules of the game - what would count as a solution. $\endgroup$ – Yuval Filmus Nov 14 '18 at 22:04
  • $\begingroup$ It can be done. Suppose $G_1$ is the PRG. Ignore $G_2$ and use a lengthening method on $G_1$. If this approach isn't admissible, please clarify the question. $\endgroup$ – Reinstate Monica Nov 15 '18 at 13:54
  • $\begingroup$ @user2712414 Just to be sure, are $\lambda$, $l$ and $\alpha$ positive integers? $\endgroup$ – John L. Nov 16 '18 at 16:56

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.