Paper 2024/116

On the practical CPAD security of “exact” and threshold FHE schemes and libraries

Marina Checri, Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France
Renaud Sirdey, Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France
Aymen Boudguiga, Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France
Jean-Paul Bultel, Université Paris-Saclay, CEA, List, F-91120, Palaiseau, France

In their 2021 seminal paper, Li and Micciancio presented a passive attack against the CKKS approximate FHE scheme and introduced the notion of CPAD security. The current status quo is that this line of attacks does not apply to ``exact'' FHE. In this paper, we challenge this status quo by exhibiting a CPAD key recovery attack on the linearly homomorphic Regev cryptosystem which easily generalizes to other xHE schemes such as BFV, BGV and TFHE showing that these cryptosystems are not CPAD secure in their basic form. We also show that existing threshold variants of BFV, BGV and CKKS are particularily exposed to CPAD attackers and would be CPAD-insecure without smudging noise addition after partial decryption. Finally we successfully implement our attack against several mainstream FHE libraries and discuss a number of natural countermeasures as well as their consequences in terms of FHE practice, security and efficiency. The attack itself is quite practical as it typically takes less than an hour on an average laptop PC, requiring a few thousand ciphertexts as well as up to around a million evaluations/decryptions, to perform a full key recovery.

Note: Added Sect. 4.4 (p. 18) which provides additional comments on the experimental results. Also added Sect. 7 (p. 25) with Sect. 7.1 mentioning concurrent work in ePrint 2024/127 and 7.2 on the application-aware approach introduced in ePrint 2024/203 following our attacks and others. We also mention new experiments on threshold OpenFHE (p. 14) and TFHE-rs (p. 16). Addtional more minor editorial modifications are also included. This paper has been accepted for publication at CRYPTO'24.

Available format(s)
Attacks and cryptanalysis
Publication info
Published by the IACR in CRYPTO 2024
FHECPADThreshold FHECCA security
Contact author(s)
marina checri @ cea fr
renaud sirdey @ cea fr
aymen boudguiga @ cea fr
jean-paul bultel @ cea fr
2024-05-30: last of 6 revisions
2024-01-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Marina Checri and Renaud Sirdey and Aymen Boudguiga and Jean-Paul Bultel},
      title = {On the practical {CPAD} security of “exact” and threshold {FHE} schemes and libraries},
      howpublished = {Cryptology ePrint Archive, Paper 2024/116},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.