In the spirit of the Kerckhoff’s principle, we consider the question: is security of an encryption scheme is still possible if the adversary has access to the decryption function , i.e., she can read the decryptions of any ciphertexts of her choice. This is well known as chosen ciphertext attack, and the security under such kind of attack can be captured by the following security game:
Note: without step 5, the game is called IND-CCA1 game and the corresponding security notion is CCA1 security.
Recall the CPA-secure encryption scheme based on PRF:
Proof. With the PRF-based encryption scheme, we can construct an adversary to exploit the decryption function to compute exactly as follows:
In step 4 of the game IND-CCA2, our adversary receives a ciphertext from Cha
Sample and
Compute
Query the decryption of . Clearly,
Adversary receives the decryption
Compute .
Then, the adversary can compute by comparing to and , and breaks the security with probability 1. ◻
Proof. Let first recall the IND-CPA game used to define the CPA-security:
With and , the game IND-CCA2 is played as follows:
Now, assume for contradiction that the encryption-then-mac scheme is not CCA-secure. That is, there is a PPT adversary that wins the above game IND-CCA2 with noticeable advantage over random guessing. We use to construct an adversary to either break or .
We consider an event : at some point in the IND-CCA2 game, submits a decryption query that is a successful existential forgery, i.e., and was never produced by the encryption oracle. We consider two possibilities:
occurs with noticeable probability: in this case, we construct an adversary to break the EUF-CMA security of .
occurs with negligible probability: in this case, we construct an adversary to break the CPA security of .
Case 1: occurs with noticeable probability. This means that is capable of forging a valid tag for a new ciphertext. Let play the EUF-CMA game while taking the role of ’s Cha in IND-CCA2 as follows:
samples and
Every time the function is called by : forwards the query to its Cha, gets the returned tag, and forwards to
When submits a decryption query , checks if it is a “fresh" query (i.e., was not produced by ’s Cha before)
As soon as submits a fresh query that is valid, outputs as its own forgery to its Cha.
Since is playing exactly an instance of IND-CCA2, there is a noticeable that event happens. It means that win EUF-CMA with noticeable probability, breaking the EUF-CMA-security of .
Case 2: occurs with negligible probability. This means that almost never produces a valid decryption query that was not produced by the encryption oracle. In this case, we let play the game IND-CPA while taking the role of ’s Cha in IND-CCA2 as follows:
samples
Every time make an encryption query for message :
requests an encryption from its cha
computes
returns to
Every time makes a decryption query, just returns
When sends :
sends these message to its Cha and receives
computes
returns to
outputs whatever outputted by .
We have that for some polynomial . This probability is noticeably better than 1/2, thus successfully breaks the CPA-security of .
In both cases, the our assumption leads to contradictions. Therefore, the encryption-then-mac scheme must be CCA-secure. ◻