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 ] [ 295 downloads ] [ 0 comments ]
@inproceedings{jintai2011algebraic,
  title={Algebraic solvers for certain lattice-related problems},
  author={Jintai Ding},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714134231845007631},
  booktitle={ITW 2011},
  pages={405-409},
  year={2011},
}
Jintai Ding. Algebraic solvers for certain lattice-related problems. 2011. In ITW 2011. pp.405-409. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220714134231845007631.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved