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.
$\begingroup$
$\endgroup$
9
-
1$\begingroup$ 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. $\endgroup$– fgrieu ♦Commented Sep 14, 2018 at 7:57
-
$\begingroup$ Yes, $X$ is the same as $x$. $\endgroup$– MktCommented Sep 14, 2018 at 8:08
-
2$\begingroup$ 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 $\endgroup$– MktCommented Sep 14, 2018 at 8:43
-
2$\begingroup$ @Mkt: you nailed it. Perhaps, answer your own question? $\endgroup$– fgrieu ♦Commented Sep 14, 2018 at 9:36
-
1$\begingroup$ 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}$ $\endgroup$– SEJPMCommented Sep 14, 2018 at 9:39
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
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.