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?

  • $\begingroup$ 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." $\endgroup$
    – Don Freecs
    Jan 14, 2022 at 22:29
  • 3
    $\begingroup$ 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. $\endgroup$ Jan 15, 2022 at 12:35
  • $\begingroup$ @ChrisPeikert Are there references on the correctness of LWE with alternative other distributions? $\endgroup$
    – BlackHat18
    Jan 15, 2022 at 15:29


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.