A question related to LWE.

[cscy117]

Hi,
While reading your blog, it mentions that the standard deviation is (\frac{\alpha q}{\sqrt{2\pi}}):

However, in Regev's paper "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography," the standard deviation is not divided by (\sqrt{2\pi}). Why is this the case?

Thank you, I look forward to your response.

[NigelSmart]

Sometimes people interchange the "Gaussian parameter" with the "Standard Deviation". I think what I wrote in the blog is correct and that Regev is thinking about "Gaussian parameter" (or maybe I got it round the wrong way, which is possible). In any case the division by sqrt(2pi) makes very little difference in practice when q is huge. Also in practice no one really uses Gaussian distributions [or even discrete Gaussians] unless one is doing lattice based digital signatures.

[cscy117]

Thank you for your response. I would like to ask another question: given an instance of LWE, (A, As + e), where solving for s from As + e = b is difficult, is it also difficult to solve for s from A(s + e) = b?

[cscy117]

We construct a matrix A, where the row vectors are orthogonal, and the covariance matrix of e is the identity matrix. Consequently, the covariance matrix of Ae is a diagonal matrix, implying that Ae = e' is a Gaussian random vector with independent components. The question now arises: Is (A, A s +e') an LWE instance?

It seems that the key issue here is whether constructing A in this way affects the security of LWE.

Thank you, I look forward to your response.