The Complexity of Algebraic Algorithms for LWE

Matthias Johann Steiner

Arora & Ge introduced a noise-free polynomial system to compute the secret of a Learning With Errors (LWE) instance via linearization. Albrecht et al. later utilized the Arora-Ge p…