Algebraic solvers for certain lattice-related problems
Jíntai Ding · 2011
In this paper, we present a new algorithm to solve algebraically the following lattice-related problems: 1) the small integer solution (SIS) problem under the condition: if the solution is bounded by an integer β in l∞norm, which we call a bounded SIS (BSIS) problem, and if the difference between the row dimension n and the column dimension m of the corresponding basis matrix is relatively small with respect the row dimension m; 2) the learning with errors (LWE) problems under the condition: if the errors are bounded - the errors do not span the whole prime finite field Fqbut a fixed known subset of size D (D <; q), which we call a learning with bounded errors (LWBE) problem. We will show that we can solve these problems with polynomial complexity.