Join Log in
Score:1
C.S. avatar Crypto

Errors for $\mathsf{LWE}$

in flag
C.S.

Why do we take Gaussian-like errors in $\mathsf{LWE}$?

Why for example we don't take uniform errors?

49
0 + 0
lwe
Score:2
avatar Crypto
in flag
Stanley

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.

0 + 0
Mark avatar
ng flag
Mark
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](https://en.wikipedia.org/wiki/Box%E2%80%93Muller_transform). One can then [round them](https://eprint.iacr.org/2017/1025) 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.
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.