International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Marina Checri , Université Paris-Saclay, CEA LIST, France
Renaud Sirdey , Université Paris-Saclay, CEA LIST, France
Aymen Boudguiga , Université Paris-Saclay, CEA LIST, France
Jean-Paul Bultel , Université Paris-Saclay, CEA LIST, France
Download:
DOI: 10.1007/978-3-031-68382-4_1 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2024
Abstract: In their Eurocrypt'21 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 proper 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.
BibTeX
@inproceedings{crypto-2024-34195,
  title={On the practical CPAD security of "exact" and threshold FHE schemes and libraries},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-68382-4_1},
  author={Marina Checri and Renaud Sirdey and Aymen Boudguiga and Jean-Paul Bultel},
  year=2024
}