Algebraic solvers for certain lattice-related problems

Jintai Ding Southern China University of technology; University of Cincinnati

TBD mathscidoc:2207.43054

ITW 2011, 405-409, 2011.10
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 F_q but 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.
No keywords uploaded!
[ Download ] [ 2022-07-14 13:42:31 uploaded by dingjt ] [ 194 downloads ] [ 0 comments ]
  title={Algebraic solvers for certain lattice-related problems},
  author={Jintai Ding},
  booktitle={ITW 2011},
Jintai Ding. Algebraic solvers for certain lattice-related problems. 2011. In ITW 2011. pp.405-409.
Please log in for comment!
Contact us: | Copyright Reserved