When researching about PQ KEM's I have come across two different definitions of indistinguishability under (adaptive) chosen ciphertext attack. IND-CCA (https://eprint.iacr.org/2017/604.pdf page 10, Kyber - https://eprint.iacr.org/2017/634.pdf page 3) and IND-CCA2 (https://eprint.iacr.org/2002/174.pdf page 4), the security experiments differ only in that the adversary, in the IND-CCA2 case, has an access to the decapsulation oracle also before he receives the challenge.

IND-CCA (cannot query $c^*$ to Decaps oracle): $$ (sk, pk) \leftarrow Gen()\\ (c^*, K_0) \leftarrow Encaps(pk), K_0 \in \mathbb{K}\\ K_1 \stackrel{$}{\leftarrow} \mathbb{K} \\ b \stackrel{$}{\leftarrow} \{0,1\}\\ b' \leftarrow A^{Decaps(sk,\cdot)}(c^*, K_b) $$ IND-CCA2 (can query anything to Decaps oracle before receiving $c^*$, then cannot query $c^*$ to Decaps oracle): $$ (sk, pk) \leftarrow Gen()\\ s \leftarrow A^{Decaps(sk,\cdot)}()\\ (c^*, K_0) \leftarrow Encaps(pk), K_0 \in \mathbb{K}\\ K_1 \stackrel{$}{\leftarrow} \mathbb{K} \\ b \stackrel{$}{\leftarrow} \{0,1\}\\ b' \leftarrow A^{Decaps(sk,\cdot)}(s, c^*, K_b) $$

$s$ is supposed to signify some information from the first stage - maybe a list of queries made.

Is there any easy explanation how do these two definitions actually differ? What is the advantage the adversary gets by being able to decrypt ciphertexts before he receives the challenge ciphertext (which he then cannot decrypt using the oracle).

The only advantage I can think of is that if in the first stage the adversary guesses the ciphertext that is going to be generated by the challenger, then he can win the game since he knows (assuming he can save it) that this ciphertext has already been queried and decrypts to key $K$. This probability is of course negligible (assuming the keyspace is large and he is polynomial) and therefore the advantage difference is negligible?

NIST in their call for proposals mentions IND-CCA2 definition (doesn't define it). Kyber in their NIST submission call the KEM IND-CCA2 with a reference to the paper linked above where the definition is IND-CCA. Is this just a naming confusion? Am I missing something and is there any real difference between these two definitions?


1 Answer 1


Looking at the Wikipedia article, with IND-CCA you get access to the oracle only until the message c* arrives (this is a non-adaptive attack), while with IND-CCA2 you can access the oracle using information from the message c* (this is an adaptive attack).

Looking at your first link, they appear to be sloppy/wrong with their terminology, and are using IND-CCA to refer to what we are calling IND-CCA2:

The notion of INDistinguishability against Chosen-Ciphertext Attacks (IND-CCA) [RS92] is now widely accepted as the standard security notion for asymmetric encryption schemes. Intuitively, IND-CCA security requires that no efficient adversary can recognize which of two messages is encrypted in a given ciphertext, even if the two candidate messages are chosen by the adversary himself. In contrast to the similar but weaker notion of INDistinguishability against Chosen-Plaintext Attacks (IND-CPA), an IND-CCA adversary is given access to a decryption oracle throughout the attack

I will add that in their paper they only refer to IND-CCA, and do not mention IND-CCA2 (IND-CCA2 only appears in the title of one of their citations)

For an example where sending queries before receiving c* is useful, let's suppose the encryption method is monoalphabetic substitution. I send the message "The quick brown fox jumps over the lazy dog" to the oracle and get the response (I am thinking here of having the oracle encrypt the message, but sending this as the ciphertext to a decryption oracle is equally useful). That allows me to determine the key used, and thus I can easily decrypt the message c* when it arrives without needing to access the oracle.

One place where being able to continue to send messages to the oracle after receiving c* helps is the Bleichenbacher attack. In this attack, the attacker sends modifications of c* to the oracle until it receives a positive reply (in this attack, the oracle only sends back "bad padding" or "ok padding" - I am leaving out a number of details here). When the attacker gets an "ok" response, then they create a new set of modifications to c* and sends them to the server, eventually being able to recreate the entire original message.

Bleichenbacher is an example of an attack that would be allowed under IND-CCA2 but not IND-CCA, since it depends on knowing the specific c* that we care about.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.