How to combine a PRG and a non-PRG to design a PRG? I'm trying to solve the following exercise:
Let $G_1, G_2: \{0,1\}^\lambda \to \{0,1\}^{\lambda + l}$ be two deterministic functions mapping $\lambda$ bits into $\lambda + l$ bits (for $l \ge 1$). You know that at least one of $G_1, G_2$ is a secure PRG, but you don't know which one. Show how to design a secure PRG $G^*:\{0,1\}^{2\lambda} \to \{0,1\}^{\lambda + l}$ by combining $G_1$ and $G_2$.
I think that $G^* := G_1(s_1) \oplus G_2(s_2), s_1, s_2 \leftarrow_{\\\$} \{0,1\}^\lambda$ could be a valid PRG. Anyway, I don't know how to prove it; probably with OTP?. How could I prove it using reduction?
I agree that indeed $G^*(s_1, s_2) = G_1(s_1) \oplus G_2(s_2)$ should be a valid PRG if one of $G_1$ or $G_2$ is a PRG.
The common definition of a PRG requires two properties: being expanding and pseudorandom.
Expanding: $G^*$ is expanding if $l &gt; \lambda$ because then $\lambda + l &gt; 2 \lambda$.
The more interesting part is whether $G^*$ is pseudorandom. Depending on how narrow your definition of a reduction proof is the following might fit it or not.
Pseudorandom: We know that at least either $G_1$ or $G_2$ is a PRG. Call the secure one $G_i$, we don't need to know which one because this will work in both cases.
The pseudorandom property of $G_i$ says that its output on uniform random input is computationally indistinguishable from random.
This means that we could replace the output of $G_i$ by a uniform random string and call the resulting PRG $G^{**}$
$$G^{**} = u \oplus G_{1-i}(s_{1-i}), u \leftarrow_{\\\$} \{0,1\}^{\lambda+l} $$
No (computationally bounded) adversary can distinguish this new $G^{**}$ from $G^{*}$ by pseudorandomness of $G_i$. The formalization of this step actually requires a reduction.
After this you can apply can use an OTP like argument and conclude the proof.
We use techniques reminiscent of game hopping proofs here. Game hopping is pretty common in cryptography proofs. For further reference: A good survey that helped me understand it is this paper