I am going through the course http://u.cs.biu.ac.il/~lindell/89-856/main-89-856.html, as it has a good lecture notes. I found exercise 2 solution a puzzling statement: it says that $G^\prime (x_1 , x_2 ) := G(x_1 ) ⊕ G(x_2)$ is a PRG, though I'm not sure why it is always the case. I get the intuition that xoring pseudorandom string with another pseudorandom string is also pseudorandom, though the formal proof is unclear to me.

Is it also true to PRG with any stretch $l$?


1 Answer 1


This follows essentially from the security of the one-time pad: if you have some arbitrary distribution $D$ over a group $G$, and the uniform distribution $U$ over the same group $G$. If $D$ and $U$ are independent, then sampling $x\gets D$, $y\gets U$ and computing $z=x\cdot y$, the resulting $z$ is distributed uniformly over $G$.

So, in fact, $G'$ doesn't even have to be $G(x_1)\oplus G(x_2)$; something like $B(x_1)\oplus G(x_2)$ for some arbitrary stretching function $B$ which doesn't necessarily have to be a PRG would be also fine.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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