CCVA2

Overview

Adaptive Chosen Ciphertext Verification Attack (CCVA2) security, also known as IND-CCVA2 or simply IND-CCVA, augments IND-CPA by granting the adversary access to a ciphertext verification oracle during both the pre-challenge and post-challenge query phases. On input , the verification oracle replies “valid” if decrypts to a message in and “invalid” if it decrypts to ; it never returns the plaintext itself. As on the CCA1.5 page, we explicitly stipulate that the challenge ciphertext may also be queried and is answered with “valid”.

Historically, the notion was first formalised by Krohn in a 1999 Harvard undergraduate thesis as illegal ciphertext attack (IND-ICA), motivated by practical attacks that leak a single validity bit per query - Bleichenbacher’s attack on RSA-PKCS#1 (CRYPTO 1998), the Hall-Goldberg-Schneier “reaction attack” on the McEliece and Ajtai-Dwork cryptosystems (ICICS 1999), and the Joye-Quisquater-Yung attack on EPOC (CT-RSA 2001). Pandey, Sarkar, and Jhanwar (SPACE 2012) subsequently re-introduced the notion under the name CCVA and focused exclusively on the adaptive case; what they call CCVA corresponds to CCVA2 here. The full implication and separation picture relating CCVA2 to the other CCA-style notions was later established by Das, Dutta, and Adhikari (ProvSec 2013).

CCVA2 sits strictly between CCVA1 and CCA2 in the indistinguishability hierarchy: the trivial chain holds by weakening each oracle in turn. CCVA2 is also not implied by CCA1 as a trivial weakening: Das et al. proved the one explicit separation (Theorem 1) - Construction I of their paper is an explicit scheme that is IND-CCVA2 but not IND-CCA1 - and the trivial chain of implications from CCA1 only gives , not . Das et al. further strengthen the separation in the other direction by showing (Theorem 3): even the conjunction of a pre-challenge decryption oracle and a both-phase verification oracle is not enough to reach the intermediate CCA1.5 notion. A full strict separation between CCA1 and CCVA2 is, to our knowledge, not stated explicitly in the paper.

Formal Definition

The IND-CCVA2 game is defined for a public-key encryption scheme in which returns on any ciphertext outside :

1. Setup. The challenger generates and gives to .
2. Phase 1 (pre-challenge): has access to a ciphertext verification oracle defined by

3. Challenge: outputs two equal-length messages . The challenger samples , computes , and sends to .
4. Phase 2 (post-challenge): retains access to and may query arbitrary ciphertexts, including the challenge ciphertext itself (which is answered with “valid” by explicit convention).
5. Guess: outputs a guess .

The advantage is defined as:

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

As with CCVA1, the notion is only meaningful when . For full-domain schemes such as plain ElGamal or Paillier, every element of is a valid encryption, the verification oracle is the constant “valid” function, and IND-CPA, IND-CCVA1, and IND-CCVA2 all coincide [Das et al., Remark 2].

Attacks & Relevance

The CCVA2 adversary is the classical reaction or judge-oracle attacker: someone who submits ciphertexts to a remote decryption endpoint and observes only accept/reject feedback, adaptively both before and after seeing the target. This is the natural abstraction of Bleichenbacher’s attack, the Hall-Goldberg-Schneier reaction attacks, and the Joye-Quisquater-Yung attack on EPOC, all of which succeed with only a one-bit validity signal.

In contrast to CCA2, which requires resistance against a full post-challenge decryption oracle, CCVA2 only demands resistance to a post-challenge validity check. This weaker requirement makes CCVA2 a useful stepping stone in the hierarchy: many schemes that fail CCA2 still satisfy CCVA2 (e.g. the Cramer-Shoup Lite scheme under DDH), and schemes whose ciphertext space already coincides with satisfy CCVA2 as soon as they are CPA-secure.

The non-trivial relationship with CCA1 is the most subtle feature of CCVA2 and is what motivates the CCA1.5 notion proposed by Das et al.: CCVA2 does not imply CCA1 (Theorem 1), no trivial implication goes from CCA1 to CCVA2, and even the conjunction of CCA1 and CCVA2 falls short of CCA1.5 (Theorem 3).

Achieving This Notion

CCVA2 security is trivially implied by CCA2 (a decryption oracle subsumes a verification oracle in both phases) and by CCA1.5 (whose Phase 1 decryption oracle is strictly stronger than the CCVA2 Phase 1 verification oracle, and whose Phase 2 verification oracle coincides with that of CCVA2). It is therefore also implied by every notion stronger than CCA1.5 in the taxonomy, including vCCA and vCCAD.

For full-domain schemes () such as plain ElGamal or Paillier, CCVA2 collapses to CPA and is achieved as soon as IND-CPA holds. Beyond full-domain schemes, the Cramer-Shoup Lite scheme is known to be IND-CCVA2 secure under the DDH assumption, and is used by Das et al. as a witness for : Cramer-Shoup Lite is simultaneously IND-CCA1, IND-CCVA2, and IND-CCA1.5, but not IND-CCA2.

In the FHE setting, a naive CCVA2 oracle would be dangerous: given a challenge ciphertext , an adversary could homomorphically evaluate a function to obtain whose validity depends on the underlying plaintext - for example via noise growth that triggers a decryption failure on one of the two challenge plaintexts but not on the other - and try to recover the challenge bit from the validity answer. Under the standard correctness assumption, however, is always non-, so such an attack does not go through on a correctly-evaluated, noise-bounded scheme. In practice CCVA2 is therefore achievable for FHE via the same route as CCA1.5: any IND-vCCA-secure scheme is IND-CCVA2-secure under correctness, because CCA1.5 CCVA2 trivially and vCCA CCA1.5 (Manulis–Nguyen). CCA2 remains out of reach for homomorphic schemes - it is the decryption oracle, not the verification oracle, that is incompatible with homomorphic evaluation.

Further Reading

The CCVA notion was first formalised by Krohn in a 1999 Harvard undergraduate thesis as illegal ciphertext attack (IND-ICA). It was later re-introduced and named CCVA by Pandey, Sarkar, and Jhanwar (SPACE 2012), who considered only the adaptive case. Das, Dutta, and Adhikari (ProvSec 2013) completed the implication/separation picture among CPA, CCA1, CCA2, CCVA1, and CCVA2, proved the key separations and , and introduced the intermediate CCA1.5 notion between CCA1 and CCA2. CCVA-style attacks in the symmetric-key setting are discussed by Hu, Sun, and Jiang (Science China 2009).