Paper 2010/581
Fast Algorithm to solve a family of SIS problem with $l_\infty$ norm
Jintai Ding
Abstract
In this paper, we present a new algorithm, such that, for the small integer solution (SIS) problem, if the solution is bounded ( by an integer $\beta$ in $l_\infty$ norm, which we call a bounded SIS (BSIS) problem, {\it and if the difference between the row dimension $n$ and the column dimension $m$ of the corresponding matrix is relatively small with respect the row dimension $m$}, we can solve it easily with a complexity of polynomial in $m$.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- SISLattice$l_\infty$ norm boundedmultivariate polynomialslinerization
- Contact author(s)
- jintai ding @ gmail com
- History
- 2010-11-18: received
- Short URL
- https://ia.cr/2010/581
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2010/581, author = {Jintai Ding}, title = {Fast Algorithm to solve a family of {SIS} problem with $l_\infty$ norm}, howpublished = {Cryptology {ePrint} Archive, Paper 2010/581}, year = {2010}, url = {https://eprint.iacr.org/2010/581} }