# Why does Learning With Errors require a bunch of samples?

Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity.

LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE is form of

$(\mathbf{A},\mathbf{sA+e}) \approx (\mathbf{A},\mathbf{r})$

My question is why the random matrix is the form $\mathbf{A} \in \mathbb{Z}_q^{m\times n}$ ($m >> n$)?

Is $m=1$ easily solved?

I think in the case of Ring LWE, $m=1$ can work.

1. The number of rows in matrix $$\textbf{A}$$ shows the number of LWE samples and $$m=1$$ means the adversary has access only to one sample. This would be a naive adversary model and would not be suitable for assessing the true hardness of the Problem. To consider a more powerful adversary model, a (seemingly) stronger definition is to assume that the adversary has access to arbitrary $$m$$ independent samples.
2. In the case of R-LWE, a single sample ($$m=1$$) takes the place of $$n$$ (correlated) LWE samples.
• Thank you. Could you elaborate your second answer? In the case of RLEW $n=m$ holds, is it really secure? – mallea Aug 15 '17 at 19:42