## Cryptology ePrint Archive: Report 2010/558

Solving LWE problem with bounded errors in polynomial time

Jintai Ding

Abstract: In this paper, we present a new algorithm, such that, for the learning with errors (LWE) problems, if the errors are bounded -- the errors do not span the whole prime finite field $F_q$ but a fixed known subset of size $D$ ($D<q$), which we call the learning with bounded errors (LWBE) problems, we can solve it with complexity $O(n^D)$.

Category / Keywords: LWE, Lattice, bounded errors, multivariate polynomials, linerization

Date: received 1 Nov 2010, last revised 2 Nov 2010

Contact author: jintai ding at gmail com

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2010/558

[ Cryptology ePrint archive ]