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)$.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
LWELatticebounded errorsmultivariate polynomialslinerization
Contact author(s)
jintai ding @ gmail com
History
Short URL
https://ia.cr/2010/558

CC BY

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},
note = {\url{https://eprint.iacr.org/2010/558}},
url = {https://eprint.iacr.org/2010/558}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.