# How small can the error be in LWE?

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?

• 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?
– Mark
Feb 12 at 20:27
• 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. Feb 12 at 20:33
• 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. Feb 12 at 21:37
• 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. Feb 15 at 22:42

## 1 Answer

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.