Relevance of Input and Ouput size of PRF on CTR mode

Question

I'm working on exercise 3.25 on Katz' book (2nd ed):

Let $F$ be a pseudorandom function such that for $k \in \{0, 1\}^n$ the function $F_k$ maps $\ell_{\text{in}}(n)$-bit inputs to $\ell_{\text{out}}(n)$-bit outputs.

(a) Consider implementing CTR-mode encryption using $F$. For which functions $\ell_{\text{in}}$, $\ell_{\text{out}}$ is the resulting encryption scheme CPA-secure?

(b) Consider implementing CTR-mode encryption using $F$, but only for fixed-length messages of length $\ell(n)$ (which is an integer multiple of $\ell_{\text{out}}(n)$). For which $\ell_{\text{in}}$, $\ell_{\text{out}}$ does the scheme have indistinguishable encryptions in the presence of an eavesdropper?

My answer is that it really does not matter: any combination of $\ell_{\text{in}}$, $\ell_{\text{out}}$ and $\ell$ will yield the mentioned security. Why do I think this? well, the proof that CTR mode is CPA-secure is presented in the book as theorem 3.32 and I'm pretty sure it only requires $F$ to be a PRF, with no restriction on the input and output sizes (even though it is presented with length-preserving PRF's), this should answer (a).

For part (b) I think something similar: the proof is not dependent on the message length (as long as it is polynomial in $n$, of course), so fixing a particular $\ell$ should not lead a vulnerability on CPA-security (let alone EAV-security).

Where am I failing? Intuition says this is not the case! for instance, if $\ell_{\text{in}}(n) = 1$ (for all $n$), then the counter can only be increased once and from there it will cycle $${\tt ctr}, {\tt ctr}+1, {\tt ctr}, {\tt ctr}+1,\ldots,$$ which should lead to an attack, doesn't it? The proof should take out these cases somehow, but I just can't see it, it seems to work without even in this case.

Answer 1

My solution

I think I've found a solution, there was a lack of comments/answers so I will post it as an answer in order to conclude this.

I'll begin with part (b).

Cycles in the counter must be avoided, that is, it must be ensured that ${\tt ctr}, {\tt ctr}+1,{\tt ctr}+2,\ldots$ never reaches ${\tt ctr}$ again. Notice that ${\tt ctr}\in \{0,1\}^{\ell_{\text{in}}(n)}$, so it must be ensured that the maximum block length $\ell(n)$ does not exceed $2^{\ell_{\text{in}}(n)}$. That's a constraint between ${\ell(n)}$ and ${\ell_{\text{in}}(n)}$. $\ ^{1}$

On the other hand, in the proof of the CPA-security of CTR mode the "birthday" term $2q(n)^2/2^n$ appears bounding the probability of a successful attack compared to guessing, where $q(n)$ is the maximum number of blocks (so $q(n) = {\ell(n)}/{\ell_{\text{out}}(n)}$). This term must be negligible, and that is the restriction between ${\ell(n)}$ and ${\ell_{\text{out}}(n)}$.

Regarding part (a), I claim that there is not any constraint between $\ell_{\text{in}}$ and $\ell_{\text{out}}$ as long as $\ell(n)$ satisfies the conditions mentioned above. This can be seen by revisiting the proof and checking that it holds independently of the polynomials $\ell_{\text{in}}$ and $\ell_{\text{out}}$ (so yes, the ratio $\ell_{\text{in}}/\ell_{\text{out}}$ can be anything).

---

$^{1}$This is assumed in the proof of CPA-security on Katz' book when they say: the values $f({\tt ctr}^∗ + 1),\ldots,f({\tt ctr}^* + \ell^*)$ used when encrypting the challenge ciphertext are uniformly distributed and independent of the rest of the experiment