# Is the XOR of PRGs sharing the same input a PRG?

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.

• 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
Commented Sep 14, 2018 at 7:57
• Yes, $X$ is the same as $x$.
– Mkt
Commented Sep 14, 2018 at 8:08
• 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
Commented Sep 14, 2018 at 8:43
• @Mkt: you nailed it. Perhaps, answer your own question?
– fgrieu
Commented Sep 14, 2018 at 9:36
• 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}$ Commented Sep 14, 2018 at 9:39

## 1 Answer

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.