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?

Improve this question
$\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, 2020 at 9:50
  • $\begingroup$ @Alex I updated the question, I think it's more clear now $\endgroup$
    – Francesco
    Nov 17, 2020 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, 2020 at 10:20
  • $\begingroup$ @Maeher I didn't write the exercise, I assume that $l > \lambda$ is implicit $\endgroup$
    – Francesco
    Nov 17, 2020 at 11:05
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – fgrieu ♦
    Nov 17, 2020 at 15:10

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

Your Answer

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

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