# Randomness of Decision Learning With Error Problem

I read the statement of the Decision Learning with error problem is:

• distinguish between $$(\vec a, \langle \vec a, \vec s \rangle + e)$$ from uniformly random samples.

Can anyone explain what does it mean to distinguish $$(\vec a, \langle \vec a, \vec s \rangle + e)$$ from random samples? Does it mean subjecting $$(\vec a, \langle \vec a, \vec s \rangle + e)$$ to some statistical test for randomness? From what I understand a and e are both randomly sampled from a uniform distribution, So why would $$\langle \vec a, \vec s \rangle + e$$ not look like random data? Is it saying that $$\langle \vec a, \vec s \rangle + e$$ is a one-way hash function?

As Peikert has commented (and my first answer was not dealing with this issue carefully), the LWE problem asks you to distinguish between $$(\vec a, \langle \vec a, \vec s \rangle + e \mod q) \in \mathbb{Z}_q^{n+1}$$ and $$\vec u \in \mathbb{Z}_q^{n+1}$$ (with each entry of $$\vec u$$ sampled uniformly from $$\mathbb{Z}_q$$) given many samples.
This is why the LWE problem is usually defined with a parameter $$m$$, which represents the number of samples $$(\vec a_i, \langle \vec a_i, \vec s \rangle + e_i \mod q)$$ that you can get. Notice that all the samples use the same fixed secret $$\vec s$$.
And about $$b_i := \langle \vec a_i, \vec s \rangle + e_i \mod q$$ being distributed uniformly on $$\mathbb{Z}_q$$, indeed, if you have a single sample, then that is the case, but again, if you have several samples, say, $$m$$, then, the distribution of $$(a_i, b_i)_{i=1}^m$$ can possibly be distinguished from the uniform over $$\mathbb{Z}_q^{n+1}$$. In particular, if you can recover $$\vec s$$, then you can simply compute $$b_i - \langle \vec a_i, \vec s \rangle \mod q$$ to get $$e_i$$, which are all small, thus, not uniformly distributed.
A final note, in your question you say "From what i understand a and e are both randomly sampled from uniform distribution", but actually, only $$\vec a$$ is uniformly chosen from $$\mathbb{Z}_q$$, the noise term $$e$$ usually follows a distribution that is likely to sample values much smaller than $$q$$ (like a Gaussian distribution with parameter approx. $$\sqrt n$$).
• I think this answer is misleading. Regarding the OP’s final questions, the point is that the attacker is given many samples with independent values of $a,e$ and the same $s$. This is absolutely critical to LWE being nontrivial. A single sample is indeed truly uniformly random, but several samples are not. “If you know $s$ (or can somehow find it)” is not relevant to the question of whether a single sample is uniformly random; it is so. Feb 20, 2020 at 16:50