You are looking at a specific version 20130608:234246 of this paper. See the latest version.

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 lattice-based 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 $\set{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 Gaussian-like distribution.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. This is the full version of a CRYPTO 2013 paper
Keywords
complexity theoryfoundationslattice techniques
Contact author(s)
daniele @ cs ucsd edu
History
2019-10-04: last of 2 revisions
2013-02-20: received
See all versions
Short URL
https://ia.cr/2013/069
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.