# Construction PRF from PRG

As discussed here, a classic and secure construction of PRF from PRG is:

$$F_k(x_1x_2\cdots x_n) = G_{x_n}(\cdots(G_{x_2}(G_{x_1}(k)))\cdots)$$

where $$G$$ is a secure pseudorandom generator. I was wondering whether the following construction is discussed anywhere (secure or insecure):

$$F_k(x) = G(k+x)$$

The $$k+x$$ could take a mod to have a fixed-length seed. Can anyone provide some proof hints or a link for discussion?

• Hint: it is possible to have a PRG $G$ such that $G(x)$ and $G(x+1)$ are strongly correlated, which of course should not happen for a PRF. – fkraiem May 24 at 13:34
• @fkraiem, I see, that makes sense. I was wondering whether most PRG implementations have this "correlated" property... – zico May 27 at 3:06
• I'm not sure it makes a lot of sense to speak of "most PRG implementations". What's a "PRG implementation", for starters? Clearly, any "implementation" of a given PRG will give the same results... – fkraiem May 27 at 7:24
• Sorry, english mistake :(. By "implementation", I actually meant "algorithm". Because you said "it is possible to have a PRG...", I was wondering whether there is any PRG such that G(x) and G(x+1) are not correlated. More generally, as long as two seeds are different, the two generated sequences "look" pseudorandom and independent, but not strongly correlated: for example, if G(x) outputs a0, a1, a2, ..., and G(x+1) outputs a0+1, a1+1, a2+1, ..., then clearly the two sequences are strongly correlated. – zico May 27 at 11:12