New answers tagged


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

Top 50 recent answers are included