There are many schemes that advertise themselves as IND-secure, but what does that mean? In this post, we will explain the IND-CPA, IND-CCA1 and IND-CCA2 security notions. We will also discuss the differences between them and when to use each one.
Preliminaries
Before we dive into security notions, let’s first define some terms that we will use throughout this post.
Without loss of generality, we will assume that an encryption scheme consists of three algorithms: a key generation algorithm $\operatorname{Key-Gen}$, an encryption algorithm $\operatorname{Enc}$, and a decryption algorithm $\operatorname{Dec}$.
The ideal functionality of an encryption scheme is to ensure that an adversary cannot learn anything about the plaintext message from the ciphertext, which means that for every ciphertext $C=\operatorname{Enc}(K,M)$, if the key remains secret for the adversary, the probability of identifying $M$ is impossible.
Since that is not possible in practice, a reasonable approach is to define constraints strong enough to satisfy some definition of security. The “IND-“ notation provides such definitions in terms of games, where a challenger keeps his key secret, and an adversary has certain capabilities and his target is to break the encryption system.
IND-CPA: INDistinguishability under Chosen Plaintext Attack
In words: the adversary generates two messages of equal length. The challenger decides, randomly, to encrypt one of them. The adversary tries to guess which of the messages was encrypted with access to a encryption oracle.
Algorithm:
- Challenger: $(pk,sk) \leftarrow \operatorname{Key-Gen}(1^n)$
- Adversary: choose two messages $M_0,M_1$ of equal length from message space $\mathcal{M}$. Send $M_0,M_1$ to the challenger. Perform additional operations in polynomial time including calls to the encryption oracle.
- Challenger: choose $b \leftarrow \{0,1\}$ and send $C^* \leftarrow \operatorname{Enc}(pk,M_b)$ to the adversary.
- Adversary: Perform additional operations in polynomial time including calls to the encryption oracle and output a guess $b’$ for $b$.
- Adversary wins if $b=b’$.
Further comment: the adversary is said to have won the game if he can guess the bit $b$ with a probability non-negligible higher than $1/2$. The encryption scheme is said to be IND-CPA secure if no polynomial-time adversary can win the game with a probability non-negligible higher than $1/2$.
IND-CCA1: INDistinguishability under Chosen Ciphertext Attack
In words: the adversary can query a encryption and decryption oracle before accepting the ciphertext. The adversary tries to guess which of the messages was encrypted.
Algorithm:
- Challenger: $(pk,sk) \leftarrow \operatorname{Key-Gen}(1^n)$
- Adversary: Perform additional operations in polynomial time including calls to the encryption and decryption oracles. choose two messages $M_0,M_1$ of equal length from message space $\mathcal{M}$. Send $M_0,M_1$ to the challenger.
- Challenger: choose $b \leftarrow \{0,1\}$ and send $C^* \leftarrow \operatorname{Enc}(pk,M_b)$ to the adversary.
- Adversary: Output a guess $b’$ for $b$.
- Adversary wins if $b=b’$.
Further comment: IND-CCA1 considers the possibility of repeated interaction, implying that security does not weaken with time.
IND-CCA2: INDistinguishability under Adaptive Chosen Ciphertext Attack
In words: In addition to its capabilities under IND-CCA1, the adversary is now given access to the oracles after receiving ciphertext, but cannot send ciphertext to the decryption oracle.
Algorithm:
- Challenger: $(pk,sk) \leftarrow \operatorname{Key-Gen}(1^n)$
- Adversary: perform additional operations in polynomial time including calls to the encryption and decryption oracles. choose two messages $M_0,M_1$ of equal length from message space $\mathcal{M}$. Send $M_0,M_1$ to the challenger.
- Challenger: choose $b \leftarrow \{0,1\}$ and send $C^* \leftarrow \operatorname{Enc}(pk,M_b)$ to the adversary.
- Adversary: Perform additional operations in polynomial time including calls to the encryption and decryption oracles, and output a guess $b’$ for $b$.
- Adversary wins if $b=b’$.
Further comment: IND-CCA2 suggests that using the decryption oracle after knowing the ciphertext can give a reasonable advantage in some schemes, since the requests to the oracle could be customized depending on the specific ciphertext.
Summary
- IND-CCA1 does not imply non-malleability (at least for the asymmetric case, Bellare et al. proved that IND-CCA1 does not imply NM-CPA)
- Two messages might not be selected randomly by the adversary.