Cryptology ePrint Archive: Report 2014/1018

Algebraic Algorithms for LWE

Martin R. Albrecht and Carlos Cid and 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.

Category / Keywords:

Date: received 23 Dec 2014, last revised 26 Feb 2015

Contact author: ludovic perret at lip6 fr

Available format(s): PDF | BibTeX Citation

Version: 20150226:151821 (All versions of this report)

Short URL: ia.cr/2014/1018

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]