Reading Introduction to Modern Cryptography by Katz and Lindell, I noticed that they talk about CPA security for block ciphers (in Section 3.6.4 where they explain mods of operation) -- and mention that most modes of operation described there are CPA-secure. Then they prove that CTR mode is CPA-secure using the key length as security parameter: "${\tt Gen}(1^n)$ chooses a random function ..." and later, in the displayed equation, $\left[ {\tt PrivK}^{cpa}_{{\cal A},\tilde\Pi}(n)=1 \right]\leq \frac{1}{2} + {\tt negl}(n)$".

However, in Chapter 5 (paragraph about "Attacks on block ciphers") they also mention that any pseudorandom permutation is secure againse CPA attacks, and that it makes no sense to use asymptotic notions of security for block ciphers, since their block and key length are fixed (and that makes perfect sense to me).

So I am confused now -- what is the point of the previous demonstrarion, on Chapter 3, that CTR mode is CPA-secure?

Or, making this question not specific to this book in particular: how do people define security against CPA (and known-plaintext, CCA etc) for block ciphers?


1 Answer 1


The book introduces two concepts, and warns not to confuse them with each other:

  1. Encryption schemes: Which can have varying key lengths; and
  2. Block ciphers: Which have fixed-length black and key lengths.

Chapter 3 of the book mainly speaks about encryption schemes. For instance, take a look at the proof of CPA-security of the CTR mode (Theorem 3.29, and Figure 3.8): The permutation $F_k$ used at the heart of the CTR construct can have varying key lengths.

However, chapter 5 mainly discusses block ciphers. These are practical constructs based on the theoretical ideas of encryption schemes (as the chapter title implies). The security of block ciphers (DES, AES, etc.) cannot be formally proved (at least at the present), since there exists no notion of concrete security, in contrast to asymptotic security.

That said, there has been some attempts at defining security notions for concrete security as well. Rogaway, for instance, has written a nice paper on defining security for "ordinary" hash functions (in contrast to "families" of hash functions).

A related question on CSTheory is Hardness Guarantees for AES, where the OP asked about provable measures for the AES block cipher.

  • $\begingroup$ OK, I get it now -- thanks a lot for your explanation! (But I feel like it's pointless to prove asymptotic security of encryption schemes if the security parameter will usually be small in practice) $\endgroup$
    – josh
    Feb 23, 2011 at 11:46
  • 2
    $\begingroup$ @josh: Yeah, all researchers had felt that it was pointless, until Rogaway found a workaround, termed "constructive" security. Though that's a story for another day :) $\endgroup$ Feb 23, 2011 at 12:45

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.