CPAD

Overview

Chosen Plaintext Attack with Decryption (CPAD) security is a seemingly mild extension of CPA security introduced for the setting of approximate Fully Homomorphic Encryption. In the CPAD game, the adversary is granted access to a highly constrained decryption oracle that accepts only legitimate ciphertexts - those produced by the encryption oracle or derived from legitimate ciphertexts through genuine homomorphic operations. The adversary also controls which homomorphic evaluations are performed.

The initial intuition is that CPAD should be equivalent to CPA: since the adversary knows the plaintext inputs of every homomorphic computation, it should be able to predict every output of this decryption oracle on its own. However, this reasoning implicitly relies on the correctness of the FHE scheme. For approximate schemes such as CKKS, decryption returns values that differ slightly from the exact plaintext, and these small differences leak information about the LWE noise embedded in ciphertexts. Li and Micciancio demonstrated that this leakage is sufficient to practically recover the secret key, showing that CPAD security is strictly stronger than CPA security for approximate FHE. While initially only targeting CKKS, CPAD attacks have been extended to all LWE/RLWE-based FHE schemes.

Formal Definition

The CPAD security game is a multi-challenge Left-or-Right game. Given a homomorphic encryption scheme , the game is parameterized by a hidden bit and maintains an initially empty state of message-message-ciphertext triplets:

1. Key generation. Run and give to .
2. Encryption request. On query , compute , return to , and set .
3. Challenge request. On query with , compute , return to , and set .
4. Evaluation request. On query with indices into , compute , , and . Return to and set .
5. Decryption request. On query with an index into : if , return . Otherwise return .
6. Guessing stage. outputs a guess . It wins if .

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

The key subtlety is that the decryption oracle returns rather than . For correct FHE these coincide, making the oracle useless and CPAD equivalent to CPA. For approximate FHE, can differ from the exact target value with non-negligible probability, so the oracle may leak information the adversary cannot compute on its own.

Attacks & Relevance

The original attack by Li and Micciancio targeted CKKS: by obtaining decryptions of legitimately computed ciphertexts, an adversary can reconstruct the secret key from the noise patterns.

More recently, Checri, Sirdey, Boudguiga, and Bultel (CRYPTO 2024) as well as Cheon, Choe, Passelègue, Stehlé, and Suvanto (CCS 2024) demonstrated that schemes previously believed immune to CPAD attacks - including the “exact” schemes BFV, BGV, and TFHE - are also CPAD-insecure as soon as decryption errors can occur with non-negligible probability. This considerably broadened the scope of CPAD as a relevant security notion beyond the approximate FHE setting.

CPAD security is relevant in any FHE deployment where the adversary can observe decrypted results of homomorphic computations it influences. This covers many practical scenarios: a client outsourcing computation to a server sees the decrypted output, and if it can choose or influence the inputs and the function being evaluated, it is effectively a CPAD adversary.

Achieving This Notion

For CKKS, Li, Micciancio, Schultz, and Sorrell (CRYPTO 2022) proposed achieving CPAD security by applying noise flooding during decryption - adding sufficiently large random noise to the decrypted value to mask the LWE error. This transforms decryption into a probabilistic algorithm and ensures the decryption oracle output does not leak exploitable information about the noise. For exact schemes where decryption errors occur, parameter choices must be carefully made so that the error probability is negligible, effectively restoring the correctness assumption that makes CPAD collapse to CPA.

Further Reading

The CPAD notion was introduced by Li and Micciancio (Eurocrypt 2021). The paper also left open the question of whether single-challenge and multi-challenge CPAD are equivalent. Brzuska et al. (CIC 2025) settled this by proving that multi-challenge CPAD is strictly stronger than single-challenge CPAD in the general (approximate) regime, i.e., . They further identified intermediate variants forming the following strict hierarchy in the general (approximate FHE) regime:

where:

• restricts the decryption oracle to close after the challenge (analogous to CCA1 vs CCA2).
• augments with a verification oracle after the challenge, which reveals whether a ciphertext is valid (decrypts to non-) without revealing the plaintext - analogous to the classical CCA1.5 (CCVA) notion of [Das, Dutta, and Adhikari (ProvSec 2013)].
• is the single-challenge variant (one challenge request with ).
• is the full multi-challenge (Left-or-Right) variant.

All separations are strict [BCF+25, Propositions 4.1, 4.3–4.7]. A more permissive verification variant (which only refuses the challenge ciphertext itself, not all challenge-related ciphertexts) is also strictly stronger than .

In the correct regime, all variants collapse: (all equivalent to CPA).

Alexandru, Al Badawi, Micciancio, and Polyakov (CIC 2026) introduced application-aware security, a weaker variant of CPAD relativized to a function class and noise estimation strategy. Bernard, Joye, Smart, and Walter (Eurocrypt 2025) introduced Strong CPAD (sCPAD) where the adversary additionally controls the encryption randomness, and showed it is strictly stronger than standard CPAD.