Appropriate error parameters for the noise flooding

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.

3 Likes