1
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ 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$ $\endgroup$
    – Alex
    Nov 17 '20 at 9:50
  • $\begingroup$ @Alex I updated the question, I think it's more clear now $\endgroup$
    – Lucio
    Nov 17 '20 at 10:03
  • 1
    $\begingroup$ A PRG is by definition expanding, so that doesn't make much sense for $l\le\lambda$. $\endgroup$
    – Maeher
    Nov 17 '20 at 10:20
  • $\begingroup$ @Maeher I didn't write the exercise, I assume that $l > \lambda$ is implicit $\endgroup$
    – Lucio
    Nov 17 '20 at 11:05
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – fgrieu
    Nov 17 '20 at 15:10
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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