Paper 2024/127
Attacks Against the INDCPA-D Security of Exact FHE Schemes
Abstract
A new security model for fully homomorphic encryption (FHE), called INDCPA-D security and introduced by Li and Micciancio [Eurocrypt'21], strengthens INDCPA 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 INDCPA-D attack on it and (erroneously) claiming that INDCPA-D security and INDCPA security coincide for FHEs on exact data. We correct the widespread belief according to which INDCPA-D attacks are specific to approximate homomorphic computations. Indeed, the equivalency formally proved by Li and Micciancio assumes that the schemes are not only exact but 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 indistinguishability and key-recovery attacks against all major exact FHE schemes. We illustrate their strength by concretely breaking the default BFV implementation of OpenFHE and simulating an attack for the default parameter set of the CGGI implementation of TFHE-rs (the attack is too expensive to be run on commodity desktops, because of the cost of CGGI bootstrapping). Our attacks extend to threshold versions of the exact FHE schemes, when the correctness is similarly loose.
Note: Submitted.
Metadata
- Available format(s)
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Contact author(s)
- damien stehle @ cryptolab co kr
- History
- 2024-02-08: last of 2 revisions
- 2024-01-29: received
- See all versions
- Short URL
- https://ia.cr/2024/127
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/127, 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{https://eprint.iacr.org/2024/127}}, url = {https://eprint.iacr.org/2024/127} }