1
$\begingroup$

Hello I'm trying to show that the function G'(s) = G(s) || G(G(s)) is not a secure PRG even if G is.

My first question is that in this case, how do I know what G is doing? Just wondering because in previous question it's been specified as a length-doubling / tripling G, but in this case I'm assuming that G is returning λ+L length string.

I know that if G is a secure PRG then L-G-prg-real and L-G-prg-rand must be indistinguishable, and that I am trying to design an attack which shows that L-G'-prg-real and L-G'-preg-rand are distinguishable. I've written G'-prg-real and G'-prg-rand like so:

L-G'-prg-real: Query(): s <- {0,1}^λ x := G(s) y := G(s) z := G(y) return x || z

L-G'-prg-rand: Query(): z := {0,1}^(λ+L) x := {0,1}^(λ+2L) return z||x

So now I'm trying to design an attack A such that when I connect it to L-G'-prg-real and L-G'-prg-rand I can distinguish between the two to prove that G' is not a secure PRG, but I'm not really getting anywhere with my current process:

I feel that I should be targeting the second half of the returned string (z), since X = G(s) in G', and we know G is a secure PRG so X is secure. In G' Y=G(s), which is used to compute Z=G(Y), Shouldn't Z just be a random string of length λ+2L since it goes through G twice?

thanks,

$\endgroup$
  • 1
    $\begingroup$ Hint: What happens if the attacker takes the first part $x$ of it's input $x\|z$ and computes $G(x)$ in the two cases? $\endgroup$ – Maeher Feb 4 at 0:59
  • $\begingroup$ @Maeher does G( G(s) ) = G(s) ? i wasn't quite sure if the definition used xor in this way $\endgroup$ – Martin Feb 4 at 3:57
  • $\begingroup$ xor? There is no mention of xor in you question. And no in all likelyhood $G(G(s))\neq G(s)$. $\endgroup$ – Maeher Feb 4 at 8:29
  • $\begingroup$ Note that to show that x(s) || y(s) is pseudo-random it is not enough to show that x(s) is pseudo-random and y(s) is pseudo-random. For example for G(s) = s || s we have that both strings are completely random, but when concatenated together they no longer look random. So even if G(s) and G(G(s)) are both pseudo-random this does not mean that G(s) || G(G(s)) is pseudo-random and the point is really to understand how they interact. $\endgroup$ – Nathan Feb 4 at 18:10

Your Answer

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

Browse other questions tagged or ask your own question.