Why do we take Gaussian-like errors in $\mathsf{LWE}$?
Why for example we don't take uniform errors?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
There are a few main reasons we use Gaussians for errors:
It makes tight security proofs easier, or at least most hardness proofs rely on the error distribution being Gaussian.
They produce small vectors that closely approximate a uniform error distribution for any lattice (see here)
There are problems with true Gaussian distributions, mainly that they can't be sampled very efficiently. This is why we tend to use 'Gaussian-like' distributions as you put it.
-
$\begingroup$ it is worth mentioning that "true gaussians" here should be read as true discrete gaussians. It is actually extremely efficient to sample true continuous gaussians, say using the Box Muller transform. One can then round them to get a distribution close to a discrete gaussian that often suffices. Note that one does lose something in doing this though --- you need higher precision sampling. This is quantified on page 37 of the linked paper. $\endgroup$– Mark Schultz-Wu ♦Commented May 16, 2022 at 23:42