# 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