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 formats: PDF | BibTeX Citation

Version: 20101103:185225 (All versions of this report)

Discussion forum: Show discussion | Start new discussion