# Can we possible to solve the LPN problem using Arora-Ge algorithm?

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.
• 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. Nov 16 '20 at 15:06
• 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. Nov 16 '20 at 22:26