I have question in learning PRG. Given that $f$ and $f_1$ are PRGs, both $\{0,1\}^n \to \{0,1\}^{2n}$.

Is $g(x) = f(x)$ xor $f_1(x)$ a PRG?

Someone told me that in this case, $g(x)$ is not a PRG, but I don't know how to prove it.

  • 1
    Is $X$ the same as $x$? Assuming so, hint: exhibit a counterexample. More precisely, assume $f$ is a PRG, and exhibit a $f_1$ that is a PRG such that $g$ is not a PRG. You won't have to stretch your imagination. – fgrieu Sep 14 at 7:57
  • Yes, $X$ is the same as $x$. – Mkt Sep 14 at 8:08
  • 2
    I might get the point that when I choose a PRG $f$ and also PRG $f_1$ same with $f$, so $g$ will always output 0, so it definitely not a PRG – Mkt Sep 14 at 8:43
  • 2
    @Mkt: you nailed it. Perhaps, answer your own question? – fgrieu Sep 14 at 9:36
  • 1
    And if you really dislike $f=f_1$, you can also choose $f_1$ as $f$ with every output bit inverted, aka $f=f_1\oplus 1^{2n}$ – SEJPM Sep 14 at 9:39

Thank you everybody's help. I have known that if $f$ and $f_1$ have some relation, then $g$ can not be PRG. e.g. $f = f_1$, then we can know, after $f ⊕ f_1$, it always return 0 for $g(x)$, in this case, $g(X)$ will never be a PRG.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.