2
$\begingroup$

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?
$\endgroup$

1 Answer 1

3
$\begingroup$
  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.

$\endgroup$
2
  • $\begingroup$ Nice answer, for large $B$ the SD becomes $o(1)$, what do you base that on? The limit of $\frac{\sigma}{\sqrt{B}}$ for $B \rightarrow \infty$ goes to 0 after all. $\endgroup$
    – Zpeed78
    Commented Jul 11, 2023 at 10:53
  • 1
    $\begingroup$ @Zpeed78 Yes, that's what little o notation means: en.wikipedia.org/wiki/… $\endgroup$
    – Daniel S
    Commented Jul 11, 2023 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.