Learning with Errors Naive Algorithm

Question

In Regev's publication "The Learning with Errors Problem", a naive algorithm is given on page 3 that can be used to tackle the LWE problem. This is the statement:

Another, even more naive algorithm is the following: keep asking for LWE samples until seeing $poly(n)$ equations of the form $s_1 \approx . . . $ (i.e., a pair $(\mathbf{a}, b)$ where $\mathbf{a} = (1, 0, . . . , 0))$, at which point we can recover the value of $s_1$. We then repeat this for all $s_i$. The probability of seeing such an equation is $q^{−n}$, leading to an algorithm requiring $2^{O(n \log(n))}$ equations.

I have a few basic questions:

• How exactly can one obtain $s_1$. If I understand correctly, we have only given samples $(\mathbf{a}$, $b = \langle a , s \rangle + e)$ and expressed them as an equation, if $\mathbf{a}$ is of the form $(1,0,...,0)$ then $b = 1 \cdot s_1 + e$, the error term $e$ now keeps us from getting the $s_1$. I can then only hope that in the $poly(n)$ equations perhaps one is of the form $b = 1 \cdot s_1 + 0$. So the question is, how do we get the $s_1$?
• Finally, how do we get that $2^{O(n \log(n))}$ equations are needed to get the total secret $s$.
• A more general question: If I think of LWE as a noisy linear system of equations, what would an application of Gaussian elimination achieve?

Answer 1

1. We can assume that we know the distribution of the errors (for example that they are distributed $\mathcal N(0,\sigma^2)$), by collecting many samples $\hat s_{1,i}$ for $i=0,\ldots,B$ we can take their average: $$\frac1B\sum_{i=1}^B\hat s_{1,i}$$ which will have mean $s_1$ and standard deviation $\sigma/\sqrt B$. For large $B$ (still no greater than $\mathrm{poly}(n)$) the standard deviation will be $o(1)$ and we should have high confidence that the nearest integer to our estimate is $s_1$.

2. We assume that $\log q=O(\log n)$ which is typical for LWE problems. The process is expected to require $1/q^{-n}$ samples to find one of the desired form. As we require $\mathrm{poly}(n)$ samples of the desired form the overall number of samples is at most $n\mathrm{poly}(n)q^{O(n)}=q^{O(n)}=2^{O(n\log n)}$

3. If we write $A=LU$ for the $LU$-decomposition of $A$ then Gaussian elimination essentially corresponds to multiplying both sides of an equation by $L^{-1}$. In the non-error case $A\mathbf x=\mathbf b$ becomes $U\mathbf x= L^{-1}\mathbf b$ and we solve for $\mathbf x$ by backsubstitution. In the LWE case $A\mathbf s+\mathbf e=\mathbf b$ becomes $$U\mathbf s+L^{-1}\mathbf e=L^{-1}\mathbf b$$ and because the entries of $L^{-1}\mathbf e$ are unknown we cannot solve for $\mathbf s$. Indeed, because little can be said about the size of the entries of $L^{-1}\mathbf e$, this is considered more problematic than the original equations.