# Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG?

If $$F$$ a PRF, and we construct $$G$$ using $$F$$ in the following way: $$G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$$ where $$|s|= n$$.

Is $$G$$ then a PRG? If so how can I prove this? If not how can $$G(s)$$ be distinguished from a random $$r$$? And what if $$n+1 <$$ range of $$F_s$$? or it could be for any $$n > |s|$$.

• Well, this question effectively is: "Is CTR a PRG"? Nov 6, 2016 at 16:35
• What have you tried? There are very many basic results which are proved in similar ways. Nov 6, 2016 at 18:07
• @fkraiem i tried to make a reduction , given adversary A(distinguisher for G) , building a distinguisher D that emulate A on F_s , and return 1 if and only if A return 1
– odu9
Nov 7, 2016 at 7:38
• Well, that's the right way. But what is the problem there? Because this works without doing a single calculation on your part. You just need to relay queries the right way. And you have the same probability of success as $A$.
– tylo
Nov 7, 2016 at 13:03
• Dec 2, 2018 at 14:56

I assume certain familiarity with the definitions of Katz and Lindell book (this is exercise 3.14 in the book). In particular, $$O$$ is denoting an oracle. It can be either a random function oracle (if $$b = 0$$) or the output of a random function $$F_s$$ (if $$b = 1$$). What you do essentially in your distinguisher is query this oracle $$l(n)$$ times. This is a generalization with respect to your setting. Instead of $$n$$ one can write an arbitrary polynomial $$l(n)$$ since the involved algorithms are PPT.
In any case, note that when you gather all the $$b_i$$ you get $$y = G(s)$$ or $$y$$ uniformly distributed in $$n \cdot l(n)$$. This is because the independent concatenation of uniformly distributed bits is uniformly distributed (?). So, indeed what you have in the last part is a distinguisher for the PRG game.
If you assume that $$G$$ is not a PRG then we can use an attack $$A$$ that has non-negligible probability $$|P[WIN_{PRG}] - \frac 1 2|$$. Then, we realize that one wins in the game PRF if and only if one wins in the PRG game (case distinction on $$b$$). Therefore, $$|P[WIN_{PRF}] - \frac 1 2| = |P[WIN_{PRG}] - \frac 1 2|$$ is non-negligible, but this contradicts the definition of PRF.