2
$\begingroup$

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

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

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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