Fast Algorithm to solve a family of SIS problem with $l_\infty$ norm

Jintai Ding

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 $β$ 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): PDF
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: SIS Lattice norm bounded multivariate polynomials linerization
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}
}

Paper 2010/581

Fast Algorithm to solve a family of SIS problem with l∞ norm

Abstract

Metadata

Fast Algorithm to solve a family of SIS problem with $l_{\infty}$ norm