Paper 2013/069
Hardness of SIS and LWE with Small Parameters
Daniele Micciancio and Chris Peikert
Abstract
The Short Integer Solution (SIS) and Learning With Errors (LWE) problems are the foundations for countless applications in latticebased cryptography, and are provably as hard as approximate lattice problems in the worst case. A important question from both a practical and theoretical perspective is how small their parameters can be made, while preserving their hardness. We prove two main results on SIS and LWE with small parameters. For SIS, we show that the problem retains its hardness for moduli $q \geq \beta \cdot n^{\delta}$ for any constant $\delta > 0$, where $\beta$ is the bound on the Euclidean norm of the solution. This improves upon prior results which required $q \geq \beta \cdot \sqrt{n \log n}$, and is essentially optimal since the problem is trivially easy for $q \leq \beta$. For LWE, we show that it remains hard even when the errors are small (e.g., uniformly random from $\{0,1\}$), provided that the number of samples is small enough (e.g., linear in the dimension $n$ of the LWE secret). Prior results required the errors to have magnitude at least $\sqrt{n}$ and to come from a Gaussianlike distribution.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in CRYPTO 2013
 DOI
 10.1007/9783642400414_2
 Keywords
 complexity theoryfoundationslattice techniques
 Contact author(s)
 daniele @ cs ucsd edu
 History
 20191004: last of 2 revisions
 20130220: received
 See all versions
 Short URL
 https://ia.cr/2013/069
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/069, author = {Daniele Micciancio and Chris Peikert}, title = {Hardness of {SIS} and {LWE} with Small Parameters}, howpublished = {Cryptology {ePrint} Archive, Paper 2013/069}, year = {2013}, doi = {10.1007/9783642400414_2}, url = {https://eprint.iacr.org/2013/069} }