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 = &lt;\vec{a}_i,\vec{s}&gt;+e_i~mod~q$ for some integer $q$, adversaries generate algebraic polynomials which has a root $e_i = b_i - &lt;\vec{a}_i,\vec{s}&gt;~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 = &lt;\vec{a}_i,\vec{s}&gt;+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.