I understand that if we have a secure PRG then the Goldreich-Goldwasser-Micali construction gives us a secure PRF.
However, what I've not been able to find much material on is how will the GGM construction fairs when the PRG is less than perfect.
Suppose we used AES-128 in CTR mode as the PRG to generate 256-bits of output for use in this construction. I don't think anyone would argue whether this was secure or not. They might say it's horribly slow but let's ignore that for now.
What happens if we replace AES-128 in CTR mode with a bad PRG. One that has a bias that's significant? Let's say we had a bias in our PRG of $ \epsilon = {1\over2^{16}}$. That would be a pretty terrible stream cipher and completely broken normally.
However, my intuition leads me to think the whole construction might even be secure with such a terrible PRG because we're only producing a stream double the key length. As such, the set of keys fed in to the next layer should still be pretty much uniform.
In fact, I'm tempted to claim that as long as there's no attack that can distinguish the PRG using only the first $2 \times k$ bits, the overall scheme is secure.
The argument goes like this:
- The key at the top of the tree is seed to the prg. This is selected at random from the set of all possible keys.
- We then feed this seed in to the prg. The prg can not be distinguished from random with the $2 \times k$ bits generated from it.
- Thus the two cells below it can not be distinguished from random.
- One of these cells then becomes the new key to the next layer down.
- Given that this key could not be distinguished from random we replace it conceptually with a real random key.
- The situation is now symmetric with step one, except we're now one step removed from the root of the tree.
- We can now re-run steps 1-6 for each level in the tree and have a provably secure prf from a horribly bias prg.
That seems like it proves too much to me; it's an absurdly strong result.
Am I right or does the construction succumb in the presence of a wonky PRG in a way I haven't anticipated?