Appropriate error parameters for the noise flooding

Hi everyone.

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.

For example, in Parameters (Concrete) of §C.2 in Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE, if the error distribution of the base scheme is bounded to [-B, B], the one for the additional error is [-B\cdot 2^λ, B\cdot 2^λ], where λ is the security parameter.

As another example, in Introduction in Sanitization of FHE Ciphertexts, a similar explanation is described.

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.

In the Palisade library, they add noise with 20-bit standard deviation: increased noise flooding parameter for CKKS Threshold FHE (!273) · Merge requests · PALISADE / PALISADE Development · GitLab

In the OpenFHE library, the standard deviation of the error distribution in the base scheme is 3.19, while the one for the noise flooding is 1048576 (= 2^{20}): openfhe-development/cryptocontextparams-defaults.h at main · openfheorg/openfhe-development · GitHub openfhe-development/rlwe-cryptoparameters.h at main · openfheorg/openfhe-development · GitHub

These 20-bit errors are not sufficient for the noise flooding according to the papers above.

I found others also have similar questions: homomorphic encryption - How to choose the large noise when using noise flooding technique in FHE? - Cryptography Stack Exchange

Do you have comments on the appropriate error parameters?

Just a heads up it looks like you’re using Latex-y symbols. Know that we now have MathJax Support!

Hope this helps :slight_smile:

Thanks for telling me about MathJax. I have rewritten inline equations in my post.

Hi @HikaruTsuchida ,

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?

1 Like

Hi @HikaruTsuchida,

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.

2 Likes

Thank you for your response. I also thank you for giving me the recent work by Li et al. and for connecting me with Mr. Nick_Genise.

Thank you for your detailed explanations. It is very helpful.

1 Like

You’re welcome! I am glad to help.

1 Like

We recently released v1.0.0 (Nov 3, 2022), where we included new flooding noise estimates. See openfhe-development/CKKS_NOISE_FLOODING.md at main · openfheorg/openfhe-development · GitHub for more details.