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$ – Javier Nov 20 '18 at 20:34
  • $\begingroup$ ics.uci.edu/~stasio/spring04/sol5.pdf $\endgroup$ – Javier Dec 2 '18 at 15:01
  • $\begingroup$ are you sure this is the correct link? $\endgroup$ – kelalaka Dec 2 '18 at 15:49

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.