Paper 2024/127

Attacks Against the INDCPA-D Security of Exact FHE Schemes

Jung Hee Cheon, CryptoLab Inc., Seoul National University
Hyeongmin Choe, Seoul National University
Alain Passelègue, CryptoLab Inc.
Damien Stehlé, CryptoLab Inc.
Elias Suvanto, CryptoLab Inc., University of Luxembourg

A recent security model for fully homomorphic encryption (FHE), called IND-CPA^D security and introduced by Li and Micciancio [Eurocrypt'21], strengthens IND-CPA security by giving the attacker access to a decryption oracle for ciphertexts for which it should know the underlying plaintexts. This includes ciphertexts that it (honestly) encrypted and those obtained from the latter by evaluating circuits that it chose. Li and Micciancio singled out the CKKS FHE scheme for approximate data [Asiacrypt'17] by giving an IND-CPA^D attack on it and claiming that IND-CPA security and IND-CPA^D security coincide for exact FHE schemes. We correct the widespread belief according to which IND-CPA^D attacks are specific to approximate homomorphic computations. Indeed, the equivalency formally proved by Li and Micciancio assumes that the schemes have a negligible probability of incorrect decryption. However, almost all competitive implementations of exact FHE schemes give away strong correctness by analyzing correctness heuristically and allowing noticeable probabilities of incorrect decryption. We exploit this imperfect correctness to mount efficient non-adaptive indistinguishability and key-recovery attacks against all major exact FHE schemes. We illustrate their strength by implementing them for BFV using OpenFHE and simulating an attack for the default parameter set of the CGGI implementation of TFHE-rs (the attack experiment is too expensive to be run on commodity desktops, because of the cost of CGGI bootstrapping). Our attacks extend to CKKS for discrete data, and threshold versions of the exact FHE schemes, when the correctness is similarly loose.

Note: Submitted.

Available format(s)
Attacks and cryptanalysis
Publication info
Fully Homomorphic EncryptionIND-CPA^D Security
Contact author(s)
damien stehle @ cryptolab co kr
2024-05-28: last of 3 revisions
2024-01-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jung Hee Cheon and Hyeongmin Choe and Alain Passelègue and Damien Stehlé and Elias Suvanto},
      title = {Attacks Against the {INDCPA}-D Security of Exact {FHE} Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2024/127},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.