# Building a CPA-secure sCTR from a PRF

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()\|\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()$$. Schematically: 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() || \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?
• $[\;\;]$ is the encoding of $x$? not clear the relation of $$ and $x$ for me. – kelalaka Nov 20 '18 at 20:31
• @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)]$ – Rodrigo Nov 20 '18 at 20:34
• ics.uci.edu/~stasio/spring04/sol5.pdf – Rodrigo Dec 2 '18 at 15:01
• are you sure this is the correct link? – kelalaka Dec 2 '18 at 15:49