Easy explanation of "IND-" security notions?

Question

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

Answer 1

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 $\operatorname{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$.

The key ($K_E,K_D)$ is a pair, also known as a [public/private] key pair. It consist of a public part $K_E$, known as the public key, used for encryption; and a secret part $K_D$, known as the private key, used for decryption. The challenger knows both the public and private keys. The adversary only knows the public key.

*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 = $ choose two messages of the same length. Send $m_0,m_1$ to the challenger. Perform additional operations in polynomial time including calls to the encryption oracle.
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 including calls to the encryption oracle. 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 negligible. 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, especially 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 (a polynomially-bounded number of times): call the encryption or decryption oracle for arbitrary plaintexts or ciphertexts, respectively
3. Adversary: $m_0, m_1 = $ 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.

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 = $ 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.

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 misleading.

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:$ returns 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 has introduced a focus on one fundamental idea. IND-CCA3 is equivalent to authenticated encryption.

Note that in the case of public-key cryptography the adversary is always given access to the public key $K_E$ as well as the encryption function $E(K_E, \cdot)$.