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:
Why is the extra Scheme (cryptosystem) based on a true random function instead of a PRF necessary?
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:
Suppose A is an adversary against the CTR Kryptosystem based on a secure PRF function
A runs the CPA-Experiment with two messages $m_0, m_1$ and recieves $(IV,c)$ from the challenger
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.
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:
Basic assumption PRF is secure
Assume an adversary A against #1
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)
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:
Basic Assumption: PRF is secure
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.
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)$)
Therefore D can succeed with more than non negligible probability distinguishing PRF and f, which breaks PRF and therefore leads to a contradiction
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.