RCCA

Overview

Replayable Chosen Ciphertext Attack (RCCA) security, also known as IND-RCCA, is a strict relaxation of the CCA2 game. Intuitively, while the CCA2 decryption oracle refuses only the challenge ciphertext, the RCCA decryption oracle refuses all ciphertexts that decrypt to one of the plaintext values submitted in the challenge request. In particular, this decryption oracle refuses to decrypt all rerandomizations of the challenge ciphertext in the context of correct schemes.

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

Formal Definition

The IND-RCCA 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 when called on ciphertext , it refuses to answer the request if .
6. outputs a guess .

The advantage is defined as:

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

Attacks & Relevance

RCCA security prevents an adversary from re-randomizing or re-encrypting a challenge ciphertext to circumvent the CCA2 restriction. While the CCA2 oracle only refuses the exact challenge ciphertext , an adversary could re-randomize into a different ciphertext with the same plaintext and submit for decryption. The RCCA oracle blocks this by refusing all ciphertexts that decrypt to or .

RCCA was introduced by Canetti, Krawczyk, and Nielsen as a notion that is strong enough for most practical applications of CCA2 security (key transport, hybrid encryption) while being more permissive toward benign ciphertext transformations such as re-randomization. It is considered by many to be the “right” security notion for encryption in practice.

For FHE, RCCA is incompatible with homomorphic evaluation: given encrypting , the adversary can compute for a function with and , then query the decryption oracle to learn and distinguish.

Achieving This Notion

RCCA security is achieved by any CCA2-secure scheme (the implication CCA2 RCCA is immediate since the CCA2 oracle is strictly more restrictive). Canetti, Krawczyk, and Nielsen also gave direct constructions based on the Cramer-Shoup framework.

For FHE, RCCA is not achievable - the same fundamental incompatibility as CCA2 applies, since the adversary can use homomorphic evaluation to produce ciphertexts with discriminating plaintexts that are not in .

Further Reading

The RCCA notion was introduced by Canetti, Krawczyk, and Nielsen (CRYPTO 2003). It sits strictly between CCA2 and vCCAD in the hierarchy of security notions. For a comparison with FHE-specific notions, see Brzuska et al. (CIC 2025).