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?

  • $\begingroup$ 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. $\endgroup$ – fkraiem May 24 at 13:34
  • $\begingroup$ @fkraiem, I see, that makes sense. I was wondering whether most PRG implementations have this "correlated" property... $\endgroup$ – zico May 27 at 3:06
  • $\begingroup$ 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... $\endgroup$ – fkraiem May 27 at 7:24
  • $\begingroup$ 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. $\endgroup$ – zico May 27 at 11:12

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.