CCA2

Overview

Chosen Ciphertext Attack 2 (CCA2) security, also known as IND-CCA2 or adaptive chosen ciphertext security, is the strongest standard indistinguishability-based security notion for encryption. It extends CCA1 by allowing the adversary to continue querying the decryption oracle even after receiving the challenge ciphertext, with the sole restriction that it may not submit the challenge ciphertext itself for decryption.

CCA2 sits at the top of the classical hierarchy of indistinguishability notions: IND-CPA IND-CCA1 IND-CCA2, where both implications are strict [BDJR97, BDPR98]. CCA2 captures a very powerful adversary model: one who can adaptively craft decryption queries based on the challenge ciphertext, attempting to extract information through related ciphertexts. This notion is considered the gold standard for general-purpose public-key encryption, although it is sometimes criticized for being too strong. As with CPA, the single-challenge and multiple-challenge variants of CCA2 are equivalent [BDPR98].

In the FHE context, CCA2 is incompatible with homomorphic evaluation. Given a challenge ciphertext encrypting , an adversary can homomorphically compute, say, for a known function , then query the decryption oracle on to recover , which trivially distinguishes from if .

Formal Definition

The IND-CCA2 security game proceeds as follows:

1. The challenger generates a key pair and gives to .
2. Phase 1 (pre-challenge): has access to a decryption oracle and may submit arbitrary ciphertexts for decryption.
3. outputs two equal-length messages .
4. The challenger samples , computes , and sends to .
5. Phase 2 (post-challenge): retains access to the decryption oracle, but may not query it on .
6. outputs a guess .

The advantage is defined as:

The scheme is IND-CCA2 secure if this advantage is negligible for all PPT adversaries.

Attacks & Relevance

CCA2 security prevents an adversary from exploiting the malleability of ciphertexts. Classic attacks thwarted by CCA2 include Bleichenbacher’s attack on RSA PKCS#1 v1.5, where an adversary multiplies a target ciphertext by known values and uses a decryption oracle (via error messages) to gradually recover the plaintext, as well as padding oracle attacks more generally. For standard (non-homomorphic) encryption, CCA2 is the expected security level in practice. It is required for secure key transport, hybrid encryption, and any setting where ciphertexts travel over channels controlled by an adversary.

For FHE, this fundamental incompatibility has driven research into relaxed CCA-type notions that accommodate homomorphic evaluation (such as CCA1, funcCPA, CPAD, or vCCA).

Achieving This Notion

For standard public-key encryption, CCA2 security is achieved through several well-known paradigms: the Cramer and Shoup (CRYPTO 1998) scheme (the first practical CCA2-secure scheme without random oracles), the Fujisaki and Okamoto (PKC 1999) transform (in the random oracle model, widely used in post-quantum KEMs such as those in the NIST standards), and OAEP for RSA-based encryption. In the lattice setting, CCA2-secure (non-homomorphic) encryption can be built from LWE using standard transformations.

Further Reading

The formal definition of CCA2 was given by Rackoff and Simon (1991), building on the CCA1 notion of Naor and Yung (1990). The Cramer and Shoup (CRYPTO 1998) cryptosystem was the first efficient construction achieving CCA2 without random oracles.