# 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 think you have to design secure PRG G* such that 2$\lambda$ maps to $\lambda+l$ and if you use $G_1 ⊕ G_2$ then isn't your input still $\lambda$
– Alex
Nov 17, 2020 at 9:50
• @Alex I updated the question, I think it's more clear now Nov 17, 2020 at 10:03
• A PRG is by definition expanding, so that doesn't make much sense for $l\le\lambda$. Nov 17, 2020 at 10:20
• @Maeher I didn't write the exercise, I assume that $l > \lambda$ is implicit Nov 17, 2020 at 11:05
• Comments are not for extended discussion; this conversation has been moved to chat.
– fgrieu
Nov 17, 2020 at 15:10

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 > \lambda$$ because then $$\lambda + l > 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