# Easy explanation of “IND-” security notions?

There are many schemes that can advertise themselves with certain security notions, usually IND-CPA or IND-CCA2, for example plain ElGamal has IND-CPA security but doesn't provide IND-CCA security.

The most common ones are the "IND-" ones, advertising security against specific classes of attackers.
Now these notion may not be that well-understood by many people so I ask hereby for a canonical answer, that explains what the following security notions mean. A (simple) description of the formal attack scenario is preferred.
Please don't restrict the answer to "you can chose this and if you can break it with this it isn't IND-CCA2". Please at least outline the formal attack (like f.ex. real-or-random). Relations between the "IND-" are explained (f.ex. IND-CCA implies IND-CPA).
The notions in question are:

• IND-CPA
• IND-CCA
• IND-CCA1
• IND-CCA2
• IND-CCA3
-
Where have you seen IND-CCA3? $\;$ – Ricky Demer Jul 3 '15 at 11:04
@RickyDemer, not that often. Until now, only every now and then in some papers. The first paper to mention it was this one I think. – SEJPM Jul 3 '15 at 11:06
Another notion is IND-CCA1. $\;$ – Ricky Demer Jul 3 '15 at 11:08
This paper by Bellare, Desai, Pointcheval and Rogaway from CRYPT'98 provides "canonical" definitions of most of these notions in the context of PKE (except for IND-CCA3) and most importantly, gives implications and separations. – cygnusv Jul 3 '15 at 11:24
No, I don't think it is a duplicate. You will not necessarily understand the precise meaning of IND-CPA just because you know what is meant by a Chosen Plaintext Attack, etc – Henrick Hellström Jul 3 '15 at 12:43

The ideal encryption scheme $E$ would be one that, for every ciphertext $C=E(K, M)$, if the key remains secret for the adversary, the probability of identifying $M$ is negligible. Since that is not possible in practice, the second most 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.

To keep it general, an encryption scheme will have a key generation algorithm $KG$, which will generate a key pair $K_E$, $K_D$, an encryption algorithm $E$ and a decryption algorithm $D$. Encryption is always revertible, but the encryption and decryption key can be different (covering public key crypto): $D(K_D, E(K_E, M))=M$

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.

Algorithm:

1. Challenger: $K_E, K_D$ = KG(security parameter)
2. Adversary: $m_0, m_1 =$ randomly choose two messages of the same length. Send $m_0,m_1$ to the challenger. Perform additional operations in polynomial time. (edited to include polynomial operations also at the beginning)
3. Challenger: $b=$ randomly choose between 0 and 1
4. Challenger: $C:=E(K_E, m_b)$. Send $C$ to the adversary.
5. Adversary: perform additional operations in polynomial time. Output $guess$
6. If $guess=b$, the adversary wins

Further comment: the main concept introduced by this scenario is the polynomial bound. Now, our expectations from crypto are weakened from probability of winning is negligible to probability of winning within a reasonable timeframe is neglible. The restriction for the messages to be of the same length aims to prevent the adversary to trivially win the game by just comparing the length of the ciphertexts. However, this requirement is too weak, specially because it assumes only a single interaction between the adversary and the challenger.

IND-CCA1: INDistinguishability under Chosen Ciphertext Attack

In words: the target of the game is the same as in IND-CPA. The adversary has an additional capability: to call an encryption or decryption oracle. That means: the adversary can encrypt or decrypt arbitrary messages before obtaining the challenge ciphertext.

Algorithm:

1. Challenger: $K_E, K_D$ = KG(security parameter)
2. Adversary (as many times as he wants): call the encryption or decryption oracle for a arbitrary plaintexts or ciphertexts, respectively
3. Adversary: $m_0, m_1 =$ randomly choose two messages of the same length
4. Challenger: $b=$ randomly choose between 0 and 1
5. Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
6. Adversary: perform additional operations in polynomial time. Output $guess$
7. If $guess=b$, the adversary wins

Further comment: IND-CCA1 considers the possibility of repeated interaction, implying that security does not weaken with time. Edited to remove: Another consequence of IND-CCA1 is non-malleability: the ciphertext cannot be tampered to be decrypted into a $M' \neq M$.

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 $C$, but cannot send $C$ to the decryption oracle.

Algorithm:

1. Challenger: $K_E, K_D$ = KG(security parameter)
2. Adversary (as many times as he wants): call the encryption or decryption oracle for an arbitrary plaintext/ciphertext
3. Adversary: $m_0, m_1 =$ randomly choose two messages of the same length
4. Challenger: $b=$ randomly choose between 0 and 1
5. Challenger: $C:=E(K_E, m_b)$Send $C$ to the adversary.
6. Adversary: perform additional operations in polynomial time, including calls to the oracles, for ciphertexts different than $C$. Output $guess$.
7. If $guess=b$, the adversary wins

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.

EDIT: Based on the comments, I changed every appearance of IND-CCA for IND-CCA1. There seems to be disagreement regarding if IND-CCA is equivalent to IND-CCA1 or IND-CCA2. The notion of IND-CCA3 is added based on the reference provided by @SEJPM. I add it for completeness, but it seems important to point out that there are few resources about it, and my interpretation could be mislead.

IND-CCA3: (authenticated) INDistinguishability under adaptive Chosen Ciphertext Attack

In words: It is not possible to create a valid forgery with non-negligible probability. The adversary is given two pairs of encryption/decryption oracles. The first pair performs the intended encryption and decryption operations, while the second one is defined as follows: $\mathcal{E}_K$: returns encryptions of random strings. $\mathcal{D}_K:$ return INVALID. Instead of being presented as a game, it is presented using the mathematical concept of advantage: the improvement of the probability of winning by using the valid oracle against the probability of success under the "bogus" oracle.

Formula: $\mathbf{Adv}^{ind-cca3}_{\pi}(A)=Pr\left[K\overset{\$}{\leftarrow}\mathcal{K}:A^{\mathcal{E}_K(\cdot),\mathcal{D}_K(\cdot)}\Rightarrow 1\right] - Pr\left[A^{\mathcal{E}_K(\$|\cdot|),\perp(\cdot)}\Rightarrow 1\right]$

Further comment: the paper where IND-CCA3 is introduced focus on one fundamental idea. IND-CCA3 is equivalent to authenticated encryption.

-
IND-CCA3. Does this enable you to add this to the answer? – SEJPM Jul 6 '15 at 18:48