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|$.

  • 1
    $\begingroup$ Well, this question effectively is: "Is CTR a PRG"? $\endgroup$
    – SEJPM
    Nov 6, 2016 at 16:35
  • $\begingroup$ What have you tried? There are very many basic results which are proved in similar ways. $\endgroup$
    – fkraiem
    Nov 6, 2016 at 18:07
  • $\begingroup$ @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 $\endgroup$
    – odu9
    Nov 7, 2016 at 7:38
  • $\begingroup$ 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$. $\endgroup$
    – tylo
    Nov 7, 2016 at 13:03
  • $\begingroup$ related crypto.stackexchange.com/questions/64209/… $\endgroup$ Dec 2, 2018 at 14:56

1 Answer 1


Consider the following game:

enter image description here

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.