I recently studied how to solve the LWE (learning with errors) using algebraic relations proposed by Arora and Ge (paper : New Algorithms for Learning in Presence of Errors). As I understood, for LWE instances of the form $\vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~q$ for some integer $q$, adversaries generate algebraic polynomials which has a root $e_i = b_i - <\vec{a}_i,\vec{s}>~mod~q$. If adversaries obtain sufficiently many polynomials, then they can recover the secret vector $\vec{s}$ using linearization technique.

Thus, I think that the Arora-Ge algorithm is also possible to solve LPN (learning parity with noise) problem since the instances are of the form $\vec{a}_i,b_i = <\vec{a}_i,\vec{s}>+e_i~mod~2$. However, I cannot find any references about the result, so I guess that I have some mistakes.

Why can't I use Arora-Ge algorithm to solve the LPN?


It is natural to wonder if Arora-Ge can break LPN, but as you suspect, it does not work. The essential problem is that, because the modulus is $q=2$, the method does not find the unique solution $s$, nor does it even narrow down the set of possible solutions.

The reason is that the first step of the algorithm converts each LPN sample into a quadratic (in $s$) equation that encodes the condition $\langle a_i, s \rangle = b_i \text{ or } b_i +1 \pmod{2}$. It then linearizes these equations and solves for $s$. However, observe that any $s’$ is a solution to these equations, because the right-hand side is always “0 or 1.” So, the system set up by the algorithm does not carry any information about $s$, from the very start.

Arora-Ge works for LWE because/when the modulus $q$ is larger than the number of possible error values. Then, the condition “$\langle a_i, s \rangle = b_i \text{ or } b_i+1 \text{ or } b_i-1 \ldots$” captures a nontrivial constraint on the secret $s$, and enough such equations can uniquely specify it.

  • $\begingroup$ Thanks a lot. I fully understood what the problem is. $\endgroup$ Nov 16 '20 at 14:58
  • $\begingroup$ oh, I have one more question. When we want to solve LWE problem using Arora-Ge algorithm, we easily generate new LWE samples by adding for small random error. (We can immediately generate new LWE samples from given LWE samplers.) Why we cannot use Arora-Ge algorithm in this case? Since we add small error, the modulus $q$ is still larger than the number of possible errors as you said, so we easily obtain $m(>n^2)$ LWE samples with a dimension $n$ that is a constraint of Arora-Ge algorithm. $\endgroup$ Nov 16 '20 at 15:06
  • $\begingroup$ When you create new samples by combining existing ones, the size of the resulting error is larger. Arora-Ge needs roughly $n^d$ samples, where $d$ is the number of possible values of the error. So, it’s not clear that there’s any benefit from using this technique, though I haven’t worked out the tradeoff carefully. $\endgroup$ Nov 16 '20 at 22:26
  • $\begingroup$ Sorry to late reply. Thank you for your kindness. $\endgroup$ Nov 19 '20 at 0:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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