CCVA1

Overview

Non-Adaptive Chosen Ciphertext Verification Attack (CCVA1) security, also known as IND-CCVA1, augments IND-CPA by granting the adversary access to a ciphertext verification oracle during the pre-challenge query phase only. On input , the verification oracle replies “valid” if decrypts to a message in and “invalid” if it decrypts to , but never reveals the underlying plaintext.

Historically, CCVA was first formalised by Krohn in a 1999 Harvard undergraduate thesis under the name illegal ciphertext attack (IND-ICA), motivated by practical attacks that extract information from a single validity bit - notably Bleichenbacher’s attack on RSA-PKCS#1 (CRYPTO 1998) and the Hall-Goldberg-Schneier “reaction attack” on the McEliece and Ajtai-Dwork cryptosystems (ICICS 1999). Pandey, Sarkar, and Jhanwar (SPACE 2012) later re-introduced the notion under the name CCVA, although they only formalised the adaptive variant. The non-adaptive case - our CCVA1 - was revisited together with its adaptive counterpart by Das, Dutta, and Adhikari (ProvSec 2013), who completed the implication and separation picture among the CPA, CCA, and CCVA notions.

CCVA1 is a natural weakening of CCA1: where the CCA1 adversary has a full decryption oracle before seeing the challenge, the CCVA1 adversary only learns a single validity bit per query. Trivially , and Das et al. proved both implications strict for the class of encryption schemes in which returns on every invalid ciphertext: (Corollary 1) and (Theorem 2).

Formal Definition

The IND-CCVA1 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): has no oracle access.
5. Guess: outputs a guess .

The advantage is defined as:

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

The formulation is only meaningful when , i.e. when the ciphertext space is strictly larger than the image of encryption. For full-domain schemes such as plain ElGamal or Paillier, every element of is a legitimate encryption of some message, the verification oracle is the constant “valid” function, and IND-CPA, IND-CCVA1, and IND-CCVA2 all collapse to the same notion [Das et al., Remark 2].

Attacks & Relevance

CCVA1 captures adversaries who, prior to seeing the challenge, can probe a system that distinguishes malformed from well-formed ciphertexts - typically via distinct error codes, timing differences, or protocol-level accept/reject signals - but who lose that access once the target is issued. It is the weakest formal notion that still rules out “reaction” and “judge-oracle” attacks of the Bleichenbacher or Hall-Goldberg-Schneier flavour in a lunchtime-style model.

In the broader CCA/CCVA hierarchy, CCVA1 plays the role of a lower anchor: it is strictly stronger than CPA (when invalid ciphertexts exist), strictly weaker than both CCA1 and CCVA2, and is implied by every stronger notion in the taxonomy (CCA1, CCA1.5, CCA2, vCCA, vCCAD). Its main theoretical interest is as the target of the separation , which closes a question that had remained open since Krohn’s original treatment for the class of schemes in which returns on every invalid ciphertext.

Achieving This Notion

CCVA1 security follows immediately from any IND-CCA1-secure scheme: the decryption oracle can always simulate the verification oracle by checking whether its output equals . It is also implied by any IND-CCVA2-secure scheme (by restricting to pre-challenge queries), and hence by every notion stronger than CCVA2 in the hierarchy.

For full-domain schemes such as plain ElGamal or Paillier, CCVA1 coincides with CPA and is achieved for free. For FHE schemes, where is typically a strict subset of , CCVA1 is a genuinely stronger requirement than CPA, although it remains compatible with homomorphic evaluation: since the CCVA1 adversary has no access to any oracle after the challenge is issued, it cannot use homomorphic evaluation of to mount the noise-based distinguishing attacks that break CCVA2 or CCA2 in the FHE setting.

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 by Pandey, Sarkar, and Jhanwar (SPACE 2012) under the name CCVA, although they only considered the adaptive variant. The non-adaptive variant CCVA1 is revisited alongside CCVA2 in Das, Dutta, and Adhikari (ProvSec 2013), which completes the implication/separation picture among CPA, CCA1, CCA2, CCVA1, and CCVA2, and introduces 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).