52 Things: Number 28: What is the IND-CCA security definition for public key encryption?

This is the latest in a series of blog posts to address the list of '52 Things Every PhD Student Should Know' to do Cryptography: a set of questions compiled to give PhD candidates a sense of what they should know by the end of their first year. We discuss IND-CCA security for public key encryption.

IND-CCA security stands for Indistinguishable Chosen Ciphertext Attack. The idea behind it is that in a secure encryption scheme, given a ciphertext, an adversary should not be able to tell what message the given ciphertext encrypts. In this model, the adversary is allowed to call the encryption and decryption oracles both before and after steps 3 and 4 below. The find-then-guess security game for public key IND-CCA is the following.

1. Generate the public and secret keys $(p_{k}, s_{k})$. The adversary A has access to the public key $p_{k}$

2. Assign $b \leftarrow \{ 0, 1\}$ privately

3. A is allowed to query the decryption oracle $Dec_{s_{k}}$ and the encryption oracle $Enc_{p_{k}}$

4. A then outputs a pair of messages $(m_{0}, m_{1})$

5. We output the encryption $c=Enc_{p_{k}}(m_{b})$

6. The adversary is allowed to enquire for more encryptions or decryptions, as in step 3, but he is not allowed to ask for the decryption of $c$

7. A outputs $b' \in \{ 0, 1 \}$. A wins if $b=b'$

We say the advantage of A is $Adv(A) = 2\mid Pr[A$ wins$] - 1/2 \mid$. A scheme is said to be IND-CCA secure if the said advantage is negligible.

There is a different version of IND-CCA, real-or-random, mentioned by Gareth in last week's post. The difference is at step 5 above, where instead of outputting the encryption of the message $m$ A asks for every time, we output an encryption of a random $m'$ of length $\mid m \mid$ if $b=0$, and an encryption of $m$ otherwise. A must then distinguish if he is in the "real" or "random" world. Advantage and security are defined similarly.

The two definitions are equivalent in the sense that if a scheme is IND-CCA secure in the real-or-random sense against an adversary A, we can construct an adversary B for the find-and-guess such that both advantages are equal. Similarly, if a scheme is find-and-guess secure against an adversary A, we can construct an adversary B such that $Adv_{find-and-guess}(A)=2 \cdot Adv_{real-or-random}(B)$.