Paper 2014/1018

Algebraic Algorithms for LWE

Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère, and Ludovic Perret

Abstract

The Learning with Errors (LWE) problem, proposed by Regev in 2005, has become an ever-popular cryptographic primitive, due mainly to its simplicity, flexibility and convincing theoretical arguments regarding its hardness. Among the main proposed approaches to solving LWE instances — namely, lattice algorithms, combinatorial algorithms, and algebraic algorithms — the last is the one that has received the least attention in the literature, and is the focus of this paper. We present a detailed and refined complexity analysis of the original Arora-Ge algorithm, which reduced LWE to solving a system of high-degree, error-free polynomials. Moreover, we generalise their method and establish the complexity of applying Gröbner basis techniques from computational commutative algebra to solving LWE. As a result, we show that the use of Gröbner basis algorithms yields an exponential speed-up over the basic Arora-Ge algorithm. On the other hand, our results show that such techniques do not yield a subexponential algorithm for the LWE problem. We also apply our algebraic algorithm to the BinaryError-LWE problem, which was recently introduced by Micciancio and Peikert. We show that BinaryError-LWE in dimension n can be solved in subexponential time given access to a quasi-linear number of samples m under a regularity assumption. We also give precise complexity bounds for BinaryError-LWE given access to linearly many samples. Our approach outperforms the best currently-known generic heuristic exact CVP solver as soon as m/n ≥ 6.6. The results in this work depend crucially on the assumption that the encountered systems have no special structure. We give experimental evidence that this assumption holds and also prove the assumption in some special cases. Therewith, we also make progress towards proving Fröberg's long-standing conjecture from algebraic geometry.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
ludovic perret @ lip6 fr
History
2015-02-26: last of 2 revisions
2014-12-31: received
See all versions
Short URL
https://ia.cr/2014/1018
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/1018,
      author = {Martin R.  Albrecht and Carlos Cid and Jean-Charles Faugère and Ludovic Perret},
      title = {Algebraic Algorithms for LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2014/1018},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/1018}},
      url = {https://eprint.iacr.org/2014/1018}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.