Let $F$ be a PRF with $n = l_{in}(n) = l_{out}(n)$.

For any PPT-encoding $[\;\;]:\mathbb{Z}_{2^n} \to \{0,1\}^n$ and any polynomial $l(n)$, $G_l(x) = F_k([1])\|\ldots\|F_k([l(n)])$ is a PRG of stretch $nl(n)$.

Conclude that $F$-sCTR is CPA-secure if $F$ is a PRF.

The way I went about this was reducing to $l(n) = 1$ which I think is unsound in the sense that one has to prove the property for every polynomial. Anyways, here is the reasoning.

If $l(n) = 1$, then assuming $\mathcal{B}$ is an attack to the PRG. We could let Alice and Bob choose a random $b \in \{0,1\}$, send the corresponding oracle to Eve which would query the oracle and sends the answer to the attack $\mathcal{B}$ to distinguish with non-negligible probability between a random string $y$ and $F_k([1])$. Schematically:

enter image description here

  1. How could I generalize this attack to any $l(n)$?

To conclude that $F$-sCTR is CPA-secure if $F$ is a PRF I would try to show that $G_l(x)$ is in fact a variable length PRG. But then, I'm unsure what values should I set $n$ and $l(n)$ to get such a machine. I would do something like this:

$G_l(x) \equiv G(x,1^s) = F_k([1]) || \ldots || F_k([s])$

where I set $l(n) = s$ and $n = 1$. However, if I look to the definition of $[\;\;]$ with $n = 1$, I have a function $[\;\;]:\mathbb{Z}_{2} \to \{0,1\}$ and that means I cannot input $s > 2$ to $[\;\;]$.

  1. How can I show that $G_l$ is a variable length PRF?
  • $\begingroup$ $[\;\;]$ is the encoding of $x$? not clear the relation of $[1]$ and $x$ for me. $\endgroup$ – kelalaka Nov 20 '18 at 20:31
  • $\begingroup$ @kelalaka as formulated in my notes there is no relation between $x$ and $[]$, the $[i]$ is just a number of indeces counting up to $[l(n)]$ $\endgroup$ – Rodrigo Nov 20 '18 at 20:34
  • $\begingroup$ ics.uci.edu/~stasio/spring04/sol5.pdf $\endgroup$ – Rodrigo Dec 2 '18 at 15:01
  • $\begingroup$ are you sure this is the correct link? $\endgroup$ – kelalaka Dec 2 '18 at 15:49
  • $\begingroup$ You might want to note that the proofs here will only apply as asymptotics in n. What is crucial to get the proof working is to note that the size of the set of n bit strings is exponential in n while l(n) is a polynomial in n. Consequently, for sufficiently large n the set of length n bit strings is far greater than l(n). i hope that helps in solving your homework. $\endgroup$ – mephisto Jan 28 '20 at 18:53

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.