Learning with Errors Naive Algorithm

Zpeed78

7/11/24, 9:04 AM

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?

129

1 + 0

lwe

Score:3

Crypto

Daniel S

7/11/24, 9:54 AM

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$.
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)}$
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.

+ 2

Zpeed78

7/11/24, 10:53 AM

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.

Daniel S

7/11/24, 11:04 AM

@Zpeed78 Yes, that's what little o notation means: https://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Learning with Errors Naive Algorithm

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.