HCCA

Overview

Homomorphic CCA (HCCA) security, introduced by Prabhakaran and Rosulek, is a security notion for homomorphic schemes that only allow evaluation of univariate (single-ciphertext-input) functions, drawn from a transformation set . Unlike all other notions in this zoo, the challenge in the HCCA game consists of a single plaintext (not a pair), and the adversary distinguishes between a normal encryption of and a “rigged” ciphertext.

The game uses auxiliary procedures - RigEnc, RigExtract, and RigDec - to manage the distinction. A rigged ciphertext looks like a normal encryption but is constructed so that applying a homomorphic transformation to it yields a ciphertext that decrypts normally in the real world () or to in the rigged world (), recovered via RigExtract. The adversary’s task is to determine which world it is in.

A central result of Prabhakaran and Rosulek (Theorem 1 of the paper) is that HCCA generalizes the standard indistinguishability-based CCA notions: when the transformation set is the single identity function, HCCA coincides with IND-CCA2, and more generally HCCA subsumes IND-CCA, gCCA, and RCCA. HCCA is thus not a “weaker” CCA flavor aimed at making homomorphism possible; it is the natural generalization that allows non-trivial while still ruling out all other malleability. For rich , however, HCCA is incomparable to these classical notions, because the classical notions would refuse transformations that HCCA legitimately allow.

HCCA is historically significant as one of the first attempts to define CCA-type security for homomorphic schemes, predating the SNARK-based vCCA approach by over a decade. Section 6 of the paper extends the definitions to binary (two-ciphertext-input) homomorphic operations and proves a negative result (Theorem 5): the natural generalisation of HCCA to binary operations is unachievable for a large class of useful homomorphisms. As a result, the HCCA framework as stated is limited to univariate evaluation, and this restriction is fundamental rather than cosmetic.

Formal Definition

The HCCA game is defined relative to a subset of univariate functions and relies on auxiliary procedures:

• : Returns where is a rigged ciphertext indistinguishable from a normal one, and is auxiliary information.
• : Determines if was obtained by applying on . Returns if so, otherwise.
• : Depends on the challenge bit .

The game proceeds as follows:

1. The challenger generates and gives to .
2. Phase 1: has access to a decryption oracle, (which returns rigged ciphertexts), and (which checks if a ciphertext is derived from a rigged one).
3. outputs a plaintext and state .
4. Challenge: The challenger samples . If : . If : .
5. Phase 2: has access to , , and , where:
   • If : .
   • If : if , and otherwise.
6. outputs a guess .

The scheme is HCCA-secure if the advantage is negligible for all PPT adversaries.

Attacks & Relevance

HCCA prevents attacks where the adversary homomorphically transforms the challenge ciphertext and submits the result for decryption. In the rigged world (), such queries return the “expected” value rather than the actual decryption, preventing information leakage through homomorphic manipulation.

The limitation to univariate evaluation means HCCA cannot model modern FHE settings where functions take multiple ciphertext inputs. This restriction is fundamental to the game structure: Theorem 5 of the paper shows that the natural generalization of HCCA to binary homomorphic operations is unachievable for a large class of useful homomorphisms, so the rigged-ciphertext approach does not straightforwardly extend.

Achieving This Notion

Prabhakaran and Rosulek gave an explicit construction of an HCCA-secure scheme under the standard Decisional Diffie-Hellman (DDH) assumption. The construction is a careful generalization of the rerandomizable RCCA-secure scheme of Prabhakaran and Rosulek (TCC 2007) and supports the group operation, as well as several related operations, as its homomorphic feature. Notably, the construction does not require SNARKs or any other non-standard machinery, in contrast to later FHE-oriented notions such as vCCA.

Further Reading

The HCCA notion was introduced by Prabhakaran and Rosulek (ICALP 2008). For a comparison with the vCCA approach, see Manulis and Nguyen (Eurocrypt 2024). For HCCA’s place in the wider FHE security landscape, including its position as a notion implied by vCCA, see Renard (PhD thesis, 2025), §2.3.3 and Fig. 2.10.