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

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
Short URL
https://ia.cr/2010/581

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

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