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.


1 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.