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.
Category / Keywords: foundations / complexity theory, foundations, lattice techniques Publication Info: This is the full version of a CRYPTO 2013 paper Date: received 13 Feb 2013, last revised 8 Jun 2013 Contact author: daniele at cs ucsd edu Available format(s): PDF | BibTeX Citation Version: 20130608:234246 (All versions of this report) Short URL: ia.cr/2013/069 Discussion forum: Show discussion | Start new discussion