Bounded Noise

cryptohack

Task: LWE instance with binary error e in {0,1}, n=25 secret variables, m=625 samples over GF(65537). Solution: Arora-Ge linearization — since e*(e-1)=0, each sample yields a quadratic equation in the secret; linearize all degree-2 monomials to get an overdetermined linear system with 351 variables and 625 equations, solve over GF(q).