Paper 2024/424

Revisiting the Security of Approximate FHE with Noise-Flooding Countermeasures

Abstract

Approximate fully homomorphic encryption (FHE) schemes, such as the CKKS scheme (Cheon, Kim, Kim, Song, ASIACRYPT '17), are among the leading schemes in terms of efficiency and are particularly suitable for Machine Learning (ML) tasks. Although efficient, approximate FHE schemes have some inherent risks: Li and Micciancio (EUROCRYPT '21) demonstrated that while these schemes achieved the standard notion of CPA-security, they failed against a variant, $\mathsf{IND}\mbox{-}\mathsf{CPA}^D$, in which the adversary is given limited access to the decryption oracle. Subsequently, Li, Micciancio, Schultz, and Sorrell (CRYPTO '22) proved that with noise-flooding countermeasures which add Gaussian noise of sufficiently high variance before outputting the decrypted value, the CKKS scheme is secure. However, the variance required for provable security is very high, inducing a large loss in message precision. In this work, we consider a broad class of attacks on CKKS with noise-flooding countermeasures, which we call ``semi-honest'' attacks, in which an adversary may submit only correctly distributed ciphertexts to the decryption oracle. The ciphertexts submitted for decryption can be fresh ciphertexts, or can be ciphertexts resulting from the homomorphic evaluation of some circuit on fresh and independent ciphertexts. Our motivation is to model an internal threat scenario where an adversary can passively access the internal randomness of the system. We analyze the concrete security of CKKS with various levels of noise-flooding in the face of such attacks. The aim of this work is to outline and precisely quantify the various trade-offs between the number of allowed decryptions before refreshing the keys, noise-flooding levels, and the concrete security of the scheme after a number of decryptions have been observed by the adversary. Due to the large dimension and modulus in typical FHE parameter sets, previous techniques even for \emph{estimating} the concrete runtime of such 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.