Paper 2026/203

Impossibility of CPAD security for a class of FHE schemes

Pierre-Emmanuel Clet, Université Paris-Saclay, CEA, LIST, Palaiseau, France

Marc Renard, Université Paris-Saclay, CEA, LIST, Palaiseau, France, ENS Paris-Saclay, Gif-sur-Yvette, France

Renaud Sirdey, Université Paris-Saclay, CEA, LIST, Palaiseau, France

Abstract

In this paper, we focus on the class of at least linearly homomorphic schemes such that their homomorphic addition operator is itself a linear operator over the ciphertext domain. This class of schemes, which we refer to as HELLHO schemes, notably encompasses the basic variant of most practically used FHE schemes such as BFV, BGV, CKKS and TFHE, as long as their mode of operation allows for homomorphic additions not immediately followed by bootstrapping, but also several extensions of them as well as other less mainstream proposals based on other assumptions. Although the aforementioned specific FHE are known to be CPAD insecure due to the existence of concrete attacks against them in that model, we first show by a simple argument that no HELLHO scheme can achieve CPAD security. Moving one step further, we also establish several counter-intuitive facts for the class of HELLHO schemes: for example that any CCA2 attack can be turned into a CPAD one or that, still only for this class of schemes, CCA1 security is equivalent to CPAD1 security (a strictly weaker ``CCA1-style'' variant of CPAD). Among other practical consequences, the results in this paper notably allow to show that instantiating the Dynamic Error Estimation (DEE) heuristic of Li et al. (Crypto'22) from any ``natural'' (R)LWE-based schemes cannot yield a CPAD secure scheme. As another notable consequence, we further exhibit a practical KRD attack on the DE-CKKS scheme, which is presently supported in OpenFHE. We conclude the paper by experimental results showing that this attack is able to perform a full key recovery on DE-CKKS in a matter of hours on an average laptop PC.

Note: See Sect. 7 for a summary of the outcome of Responsible Disclosure. 19/03/2026: additional considerations on sCPAD security (towards end of Sect. 4.1 and 4.3). 27/05/2027: added comments on 2026/316 on p. 17 and Sect. C.3 on (DE-)CKKS encoding.

@misc{cryptoeprint:2026/203,
      author = {Marina Checri and Pierre-Emmanuel Clet and Marc Renard and Renaud Sirdey},
      title = {Impossibility of {CPAD} security for a class of {FHE} schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/203},
      year = {2026},
      url = {https://eprint.iacr.org/2026/203}
}