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:
- 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 $[\;\;]$.
- How can I show that $G_l$ is a variable length PRF?
