Question on the CPA-security proof of the CTR-Mode

Question

While reading Katz & Lindell's textbook (2nd edition) I found a proof for the CPA-Security of CTR-Mode. It can be found at the end of chapter 3.6.2 (page 93 and 94). I don't quite understand, why the proof is that complex, so I got two basic questions about it:

1. Why is the extra Scheme (cryptosystem) based on a true random function instead of a PRF necessary?

2. Why do we want to proof it with CPA-security for multiple messages? As far as I know, CPA-security for single messages implies CPA-security for multiple messages and vice versa. Therefore that just makes is unneccesary complex.

Why can't the proof be done simpler? The sketch of my idea would be:

1. Suppose A is an adversary against the CTR Kryptosystem based on a secure PRF function

2. A runs the CPA-Experiment with two messages $m_0, m_1$ and recieves $(IV,c)$ from the challenger

3. A can use its encryption Oracle for a polynomial amount of time $p(n)$ and gets, for simplicity, $n$ duples $(IV_i,c_i)$. That leads to 2 cases: 1. An overlap occurs. Because A does not only succeeds, if $IV = IV_i$ but also if $IV+x = IV_i+y$ (for some $x,y \geq 0$, because of the counting factor of CTR-Mode). So this happens in $2p(n)^2/2^n$ instead of $p(n)/2^n$ (birthday paradox, because of $IV+x = IV_i+y$). As probability to win in that case is 1, but the probability for this case is negligible: $2p(n)^2/2^n \in negl(n)$ 2. There is no overlap and A probability to win is $1/2$, because the PRF is secure.

4. Combining these two cases the probability of A to win is $1/2 + negl(n)$, which means, that CTR is CPA secure.

Edit: Thank you for the answer! They helped me a lot in understanding the topic. But this led to another question related to this:

My professor proofed CPA-security for Encryption #1 based on PRF via a reduction proof using contradiction. The basic idea:

1. Basic assumption PRF is secure

2. Assume an adversary A against #1

3. Use A to build a distinguisher D to solve the the basic Assumption (D plays the CPA-game with A and therefore can break PRF)

4. Contradiction leads to proof if CPA-security

Because the proof in the book is based on the proof of the CPA-secure PRF-encryption, it should be possible to construct a proof, based on the the proof of the CPA-secure PRF-encryption using contradiction, right?

I give it a try:

This leads me to the following: A solution using contradiction would be more intuitiv (and I could understand it). So now therefore I give it a try:

1. Basic Assumption: PRF is secure

2. Assume an adversary A breaking the the encryption. A is able to use an encrpytion orakle (because we want to proof CPA-security). Let a have a non negligible success probability.

3. Using A we an build a distinguisher D breaking the PRF: D gets function not knowing weather it is a PRF or a true random function f. D simulates the CPA game with A using PRF or f. This leads to two cases:

3.1 D got a PRF. D is using the PRF-encryption scheme. A can break it with non negligible probability and D outputs what A ouputs.

3.2 D got a true random function. Now it gets funny: D firstly has to construct a new encrpytion scheme. For that he uses the old and just uses f instead of PRF. But now A can't win the game with more than a negligible probability: A can make p(n) many encryptions getting. Now the same argument as above can be used for overlapping (Because A does not only succeeds, if $IV = IV_i$ but also if $IV+x = IV_i+y$ (for some $x,y \geq 0$, because of the counting factor of CTR-Mode). So this happens in $2p(n)^2/2^n$ instead of $p(n)/2^n$ (birthday paradox, because of $IV+x = IV_i+y$). As probability to win in that case is 1, but the probability for this case is negligible: $2p(n)^2/2^n \in negl(n)$)

4. Therefore D can succeed with more than non negligible probability distinguishing PRF and f, which breaks PRF and therefore leads to a contradiction

5. Now only ING-CPA-security for single messages was shown, but because ING-CPA-security for single messages implies ING-CPA-security for multiple messages, we also showed that.

Answer 1

The problem is with your statement "There is no overlap and A probability to win is $1/2$, because the PRF is secure." What does that mean? The only way to formalize that is to show that if adversary wins with probability greater than $1/2$ when there is no overlap, then you can break the PRF. That is essentially what the proof does. Note that it doesn't have to be by contradiction - it's also possible to show that when there is no overlap, then a reduction to distinguishing the PRF from random shows that the gap is negligible. That is the way the proof written in the book works.

Answer 2

Why is the extra Scheme (cryptosystem) based on a true random function instead of a PRF necessary?

I don't have the book in front of me but every time you analyze the security of a PRF-based scheme, you always consider replacing the PRF with a truly random function as a conceptual step in the proof. A PRF is indistinguishable from a truly random function, so CTR mode based on a PRF is indistinguishable from CTR mode based on a truly random function. The latter is easier to analyze.

Why do we want to proof it with CPA-security for multiple messages? As far as I know, CPA-security for single messages implies CPA-security for multiple messages and vice versa. Therefore that just makes is unneccesary complex.

This is true only for public-key encryption, not symmetric-key encryption. One-time pad is secure against single messages but obviously is not CPA secure.

Why can't the proof be done simpler? The sketch of my idea would be ...

Your proof sketch is a sketch of the standard proof. It just requires more details to actually make it into a complete proof.

For example, you say that when there is "no overlap" [of the PRF inputs], the "probability to win is 1/2, because the PRF is secure." This is not a "direct" consequence of the PRF security definition. The only way to prove it formally is to argue that (1) the PRF is indistinguishable from a truly random function (this is all that the PRF security definition says); (2) in CTR mode with a truly random function, when there are no repeats among the PRF-inputs, all ciphertext blocks are truly uniformly random (using the fact that they are XOR of plaintext with independent outputs of the random function); (3) when the ciphertext blocks are uniformly random, the adversary's success probability is exactly 1/2. There is really no more direct way to argue this formally.