Score:2

Centrality of Gaussian distribution for LWE error

sy flag

Consider the LWE problem.

Let $A$ be an $m \times n$ matrix, $x$ is an $n \times 1$ vector, $u$ is a $m \times 1$ vector, and $e$ is sampled from a Gaussian distribution.

We are given either $Ax + e ~~(mod~q)$ or $u ~(mod~q)$ the conjecture being that it is difficult to distinguish between these samples in polynomial time, with high probability over the choice of $A$, $x$, $u$ and $e$ (for appropriate choices of $m$ and $q$.)

I wanted to ask about the centrality of the Gaussian distribution while considering the security of LWE.

Is LWE hard if $e$ is sampled from other distributions — like the uniform distribution or the exponential distribution?

Don Freecs avatar
sz flag
https://eprint.iacr.org/2015/939.pdf look at the page 40 "Note that this original error e can come from any distribution, as long as it is relatively short."
Chris Peikert avatar
in flag
That quote is about the correctness of a procedure for generating fresh LWE samples from some given ones. It’s not about the security of LWE with alternative error distributions.
BlackHat18 avatar
sy flag
@ChrisPeikert Are there references on the correctness of LWE with alternative other distributions?
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.