Welcome to the resource topic for 2024/424
Title:
On the Concrete Security of Approximate FHE with Noise-Flooding Countermeasures
Authors: Flavio Bergamaschi, Anamaria Costache, Dana Dachman-Soled, Hunter Kippen, Lucas LaBuff, Rui Tang
Abstract:Approximate fully homomorphic encryption (FHE) schemes such as the CKKS scheme (Asiacrypt '17) are popular in practice due to their efficiency and utility for machine learning applications. Unfortunately, Li and Micciancio (Eurocrypt, '21) showed that, while achieving standard semantic (or \mathsf{IND}\mbox{-}\mathsf{CPA} security), the CKKS scheme is broken under a variant security notion known as \mathsf{IND}\mbox{-}\mathsf{CPA}^D. Subsequently, Li, Micciancio, Schultz, and Sorrell (Crypto '22) proved the security of the CKKS scheme with a noise-flooding countermeasure, which adds Gaussian noise of sufficiently high variance before outputting the decrypted value. However, the variance required for provable security is very high, inducing a large loss in message precision.
In this work, we ask whether there is an intermediate noise-flooding level, which may not be provably secure, but allows to maintain the performance of the scheme, while resisting known attacks. We analyze the security with respect to different adversarial models and various types of attacks.
We investigate the effectiveness of lattice reduction attacks, guessing attacks and hybrid attacks with noise-flooding with variance \rho^2_{\mathsf{circ}}, the variance of the noise already present in the ciphertext as estimated by an average-case analysis, 100\cdot \rho^2_{\mathsf{circ}}, and t\cdot \rho^2_{\mathsf{circ}}, where t is the number of decryption queries. For noise levels of \rho^2_{\mathsf{circ}} and 100\cdot \rho^2_{\mathsf{circ}}, we find that a full guessing attack is feasible for all parameter sets and circuit types.
We find that a lattice reduction attack is the most effective attack for noise-flooding level t\cdot \rho^2_{\mathsf{circ}}, but it only induces at most a several bit reduction in the security level.
Due to the large dimension and modulus in typical FHE parameter sets, previous techniques even for estimating the concrete security of these attacks – such as those in (Dachman-Soled, Ducas, Gong, Rossi, Crypto '20) – become computationally infeasible, since they involve high
dimensional and high precision matrix multiplication and inversion. We therefore develop new techniques that allow us to perform fast security estimation, even for FHE-size parameter sets.
ePrint: https://eprint.iacr.org/2024/424
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .