gCCA

Overview

Generalized Chosen Ciphertext Attack (gCCA) security, introduced by An, Dodis, and Rabin at Eurocrypt 2002, is a very slight relaxation of CCA2 designed to repair a definitional shortcoming of the standard notion. The authors observed that the usual CCA2 attack model - in which the adversary is disallowed from submitting only the exact challenge ciphertext to the post-challenge decryption oracle - is not robust to harmless syntactic modifications of a scheme. For example, taking a CCA2-secure scheme and appending a trailing useless random bit to every ciphertext immediately breaks CCA2-security: the adversary can flip that bit on the challenge to obtain a different ciphertext that still decrypts to , ask the oracle to decrypt it, and win trivially. Intuitively, nothing was broken, yet the definition rules the modified scheme “insecure”.

The fix proposed by An, Dodis, and Rabin is to parameterize the CCA2 game by an efficient decryption-respecting equivalence relation over ciphertexts, and to forbid the adversary from submitting any post-challenge query with (rather than only ). Taking to be equality recovers standard CCA2; taking to identify ciphertexts that differ only in a trailing useless bit fixes the counter-example above. A scheme is gCCA-secure if some such relation exists for which the parameterized game is won only with negligible advantage.

An, Dodis, and Rabin argue that gCCA suffices for all known applications of CCA2-secure encryption while no longer suffering from the definitional fragility of CCA2 under syntactic rewrites. The same notion was proposed independently - under the name benign malleability - by Shoup for the ISO 18033-2 public-key encryption standard.

Formal Definition

A binary relation over the ciphertext space is called decryption-respecting if it is reflexive and, for all ciphertexts :

The relation may depend on the public key but must be efficiently computable without knowledge of . The IND-gCCA game for an encryption scheme with respect to proceeds as follows:

1. The challenger generates 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 any query satisfying is rejected.
6. outputs a guess .

The advantage is defined as:

The scheme is IND-gCCA-secure if there exists an efficient decryption-respecting relation such that the above advantage is negligible for every PPT adversary . Since reflexivity forces to rule out at least , standard IND-CCA2 is recovered as the special case where is the equality relation, which immediately gives .

An, Dodis, and Rabin also introduce a non-malleability analogue, , obtained by relaxing the standard non-malleability game in the same way (the adversary is not deemed successful if its output ciphertext is -equivalent to the challenge). They show that , mirroring the classical equivalence of Bellare, Desai, Pointcheval, Rogaway (CRYPTO 1998), which justifies using indistinguishability as the primary notion.

Attacks & Relevance

The original motivation for gCCA is definitional, not attack-driven: the aim is to rule out scheme-level syntactic triviality (such as the useless-trailing-bit counter-example) while still preventing every meaningful chosen-ciphertext attack that CCA2 prevents. In particular, classical attacks that CCA2 is designed to thwart - Bleichenbacher-style padding oracles, ciphertext mauling via homomorphic structure, and related-ciphertext attacks - remain blocked under gCCA, since any successful attack on gCCA translates into a meaningful non-equivalent decryption query. An, Dodis, and Rabin use gCCA as the right-level abstraction for proving the security of generic signcryption compositions such as (encrypt-then-sign) and (sign-then-encrypt) in the public-key setting, where CCA2 would have failed the proofs only for the syntactic reasons described above.

In the FHE context, gCCA remains incompatible with homomorphic evaluation for the same reason as CCA2. Given a challenge encrypting , the adversary can homomorphically compute for a function with . Since decrypts to , no decryption-respecting relation can satisfy , so is never rejected by the gCCA oracle and decrypting it trivially reveals . The fundamental tension between adaptive post-challenge decryption access and homomorphic malleability is therefore not resolved by the gCCA relaxation - it is exactly the reason FHE-oriented notions such as vCCA and vCCAD drop the requirement that the filtering relation be decryption-respecting and replace it with a SNARK-based witness extractor over homomorphic derivations.

Achieving This Notion

Any IND-CCA2-secure encryption scheme is immediately IND-gCCA-secure (under the equality relation), so all the classical CCA2 constructions - Cramer-Shoup, Fujisaki-Okamoto, OAEP, and lattice-based KEMs - yield gCCA-secure schemes. The converse does not hold: An, Dodis, and Rabin exhibit gCCA-secure schemes that are not CCA2-secure, precisely the “append a useless bit to a CCA2-secure scheme” family and similar syntactic modifications. They remark, however, that they are not aware of any natural encryption scheme that sits in the gap between gCCA and CCA2 - the separating examples are always obtained by artificially degrading a CCA2-secure scheme.

As a standardized instance, Shoup’s benign malleability variant in ISO 18033-2 uses a concrete efficient relation that identifies ciphertexts differing only in operationally meaningless components, providing a practical gCCA-secure encryption standard without requiring strict CCA2.

Further Reading

The gCCA notion was introduced by An, Dodis, and Rabin (Eurocrypt 2002) as part of their formal study of signcryption, where it was used to prove the security of generic encrypt-then-sign and sign-then-encrypt compositions in the public-key setting (under the original name generalized CCA2, denoted ). The closely related benign malleability formulation was proposed by Shoup for ISO 18033-2. For the classical equivalence between indistinguishability and non-malleability that gCCA preserves (in the form ), see Bellare, Desai, Pointcheval, and Rogaway (CRYPTO 1998). For the FHE-oriented reframing of ciphertext-filtering relaxations, where the decryption-respecting restriction is dropped in favour of a SNARK-based extractor over homomorphic evaluations, see Manulis and Nguyen (Eurocrypt 2024) on vCCA and Brzuska et al. (CIC 2025) on vCCAD.