2
$\begingroup$

For modulus $Q$ and stddev $\sigma$, [GHS12] suggests that, to achieve 128-bit security, just choose the dimension $N$: $$ N\geq(Q/\sigma)\cdot 33.1 $$

This seems to suggest flexibility to choose smaller $\sigma$ ("as long as it is not too tiny"), but just paying a price on $N$.

Many instantiations seem to favor a fixed $\sigma$ about $3.2$ ([GHS12]). Especially, the homomorphic encryption standard said:

The standard deviation that we use below is chosen as $\sigma = 8/\sqrt{2}\pi \approx 3.2$, which is a value that is used in many libraries in practice and for which no other attacks are known. (Some proposals in the literature suggest even smaller values of $\sigma$.)

There are schemes using a smaller $\sigma$. Frodo is looking at approximating $\sigma\approx1$.

My question:

In my use case, I do need the noise to be very small.

  • Can one do $\sigma\approx0.1$?
  • If not, how small can $\sigma$ be, if one needs to minimize it?
  • Is it because we need to approximate continuous Gaussian, so $\sigma$ can never be too small?

Note that $\sigma\approx 0.1$ seems unreasonable, since, with a high possibility, all sampled values will be zero (by making it an integer). And [GHS12] mentions explicitly that the $N\geq(Q/\sigma)\cdot 33.1$ check does not apply to "too tiny $\sigma$", although the paper did not explicitly mention what is considered "too tiny".

Yet, the LWE estimator seems "okay" with $\sigma\approx0.1$. I guess small $\sigma$ is beyond the scope of the LWE estimator?

$\endgroup$
4
  • 1
    $\begingroup$ I am not too familiar with the LWE estimator, but it seems that it has a function for evaluating the "Small $\sigma$" attack (the Arora-Ge attack). Do you get different results when you call that directly? $\endgroup$
    – Mark
    Feb 12 at 20:27
  • $\begingroup$ Great points! Just notice that by default, the LWE estimator did not run 'mitm', 'arora-gb', 'bkw`. They are likely heavy---as I am still running and waiting for the results. Will keep you posted. $\endgroup$ Feb 12 at 20:33
  • 1
    $\begingroup$ An update: the estimator for the Arora-Ge attack is still running. Have the feeling that this one is going to take a fairly long time. Still, I will keep you posted when more results come out. $\endgroup$ Feb 12 at 21:37
  • $\begingroup$ Update: For small parameters (q~20000), the estimator allows smaller stddev like 1 and 0.8 and does display a security loss between them. However, for q that is pretty large in my case (q~2^64), the estimator cannot compute for small stddev ("insufficient samples" or something like that), and computing for stddev=4 is still running. I feel I would need to find some approximation algorithms/simplified models for Arora-Ge attack. $\endgroup$ Feb 15 at 22:42
0
$\begingroup$

Per Mark's suggestion, I looked into the "hidden" tests in lwe-estimator and read a few papers. I summarized my findings as an answer here:

  • Arora-Ge attack, and the improved version using Grobner bases, work better when $q$ is small, but it starts to be impractical once the number of samples $n$ and $q$ is very large, e.g., $q=2^{64}$. This seems to be due to the time needed for linearization.

  • Another hidden test, MITM (Section 5.1 in https://eprint.iacr.org/2015/046.pdf), can be useful here---MITM considers $\alpha q$, and it is important that $\alpha$ cannot be way too small. Reflected in lwe-estimator, this would disallow one to use $\sigma\approx0.001$.

Still, more discussion is welcome. For my own use case, it seems that $\sigma=1$ or $\sigma\approx0.8$ may be generally okay since my $q$ is large.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.