Solving LWE problem with bounded errors in polynomial time

Jintai Ding

Paper 2010/558 Original: eprint.iacr.org/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)$.

Metadata

Available format(s): PDF
Publication info: Preprint.
History: 2010-11-03: last updated; 2010-11-03: published
Short URL: https://ia.cr/2010/558
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2010/558,
      author = {Jintai Ding},
      title = {Solving LWE problem with bounded errors in polynomial time},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/558},
      year = {2010},
      url = {https://eprint.iacr.org/2010/558}
}