A New Algebraic Algorithm for LWE
Abstract
The Learning With Errors (LWE) problem, introduced by Regev in 2005, is central to modern cryptography and post-quantum security. The algorithms to solve the search version of the problem, Search-LWE, can be broadly categorised into algebraic, combinatorial and lattice-based. In this work we propose a new algebraic algorithm for the Search-LWE problem. At a high level, the algorithm combines linear-algebraic techniques with S-polynomial-based methods from Groebner basis computation. We provide a direct complexity analysis of our algorithm, avoiding semi-regularity assumptions and complexity bounds derived from the degree of regularity. Our algorithm achieves a polynomial improvement in complexity over prior results that use Groebner basis methods to solve Search-LWE.
Related
- A Low-rank ADI Algorithm for the Numerical Solution of Large Discrete-time Non-symmetric Algebraic Riccati Equations
- An Algebraic Matching Algorithm for the Genus of Grid Diagrams
- D-RADI: A Low-rank ADI Algorithm for Solving Large-scale Discrete-time Algebraic Riccati Equations
- Duals of algebraic matroids need not be algebraic
- Birational Algebraic Topology
BibTeX
@misc{campa2026algebraic,
title = {{A New Algebraic Algorithm for LWE}},
author = {Luca Campa and Massimo Fumiani and Arnab Roy},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29977},
eprint = {2608.29977},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29977},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - A New Algebraic Algorithm for LWE
AU - Luca Campa
AU - Massimo Fumiani
AU - Arnab Roy
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29977
UR - https://arxiv.org/abs/2608.29977
AB - The Learning With Errors (LWE) problem, introduced by Regev in 2005, is central to modern cryptography and post-quantum security. The algorithms to solve the search version of the problem, Search-LWE, can be broadly categorised into algebraic, combinatorial and lattice-based. In this work we propose a new algebraic algorithm for the Search-LWE problem. At a high level, the algorithm combines linear-algebraic techniques with S-polynomial-based methods from Groebner basis computation. We provide a direct complexity analysis of our algorithm, avoiding semi-regularity assumptions and complexity bounds derived from the degree of regularity. Our algorithm achieves a polynomial improvement in complexity over prior results that use Groebner basis methods to solve Search-LWE.
ER -