I have a question about the noise flooding technique in FHE.
In threshold FHE schemes, parties add a noise sampled from a distribution that has larger standard deviation or bound parameters than the ones in the base scheme.
However, in the Palisade and the OpenFHE libraries, it appears to me that the additional noise is not sampled from a distribution with a sufficient large standard deviation.
Thank you for the question. It is correct that a 20-bit standard deviation is currently used for threshold FHE decryption in OpenFHE. It is also correct that adding 20 bits of noise is not sufficient to achieve 128 bits of security in the general case. We chose this value in the current implementation for efficiency reasons, assuming that a large number of distributed threshold FHE queries would not be allowed for the same or related ciphertexts by the application (all parties need to be involved in each threshold FHE decryption). While 20 bits may arguably give practical security under this assumption, we are currently looking into higher noise parameters that would satisfy the noise flooding requirements described in literature. We want to implement these refined noise parameters (not just for threshold FHE, but also for PRE and IND-CPA^D security in CKKS) before v1.0.0 is released later this year.
A recent work by Li et al. (Securing Approximate Homomorphic Encryption Using Differential Privacy) suggests that we do not have to set the noise distribution parameter to a value higher than 2^\lambda to achieve \lambda bits of security. For instance, the authors suggest that adding 45 bits of noise may be sufficient to achieve 128 bits of security. @Nick_Genise is currently looking into this problem and can provide further details. @Nick_Genise, could you briefly describe the substantiation for using a smaller parameter for noise flooding and provide any further relevant clarifications?
Background: using statistical distance yields a crude bound of \sigma B noise bits for \sigma = 2^\lambda, and Micciancio and Walter’s 2018 Eurocrypt paper implies that \sigma = 2^{\lambda/2} is sufficient. Li et al.'s work takes this further and applies it to the IND-CPA^D setting which is the same as the threshold FHE setting, even in BGV/BFV or plain LWE (we flood to protect the ciphertext noise).
Some more details about the Li et al. paper: they separate the computational security from statistical security described in-detail in Section 4.4. They call this (\lambda,s) where a scheme uses a \lambda-bit secure computational assumption (e.g., RLWE) and a s-bit secure statistical assumption (regardless of an adversary’s time resources). That is, s means that any adversary has at most 2^{-s} success probability. Here is where they argue that (just under) 47 bits of noise flooding is secure in most settings. This is from the formula
\sigma = \sqrt{24n\alpha}2^{s/2}
where \alpha is the number of threshold decryption queries, n is the RLWE ring dimension, and s is the statistical security (an adversary has 2^{-s} chance of success). Let, n = 2^{15} and restrict \alpha = 1, then this is about 10 + s/2 bits for \sigma. So, 20 bits in openFHE corresponds to roughly 2^{-20} (s=20) success chance for any adversary. Maybe s should be something like 30, which would correspond to a 2^{-30} success chance (~one in a billion) and \sigma=25.
I want to note that there is a 128-bit version of CKKS in openFHE which allows you to blow past the \Delta m + e\leq 2^{64} restriction imposed by 64-bit native arithmetic for about a 4x slowdown. This would easily allow for \sigma = 47 (s = 64 with \alpha = 2^{10}) from Section 4.4 in Li et al. Increasing the flooding noise in BGV/BFV doesn’t require 128-bit arithmetic since you would simply decrypt with an extra RNS modulus or two.
