In this paper, we improve the algorithm proposed by Albrecht et al. by using multidimensional Fourier transforms. Our algorithm is, to the best of our knowledge, the fastest LWE solving algorithm. Compared to the work of Albrecht et al. we greatly simplify the analysis, getting rid of integrals which were hard to evaluate in the final complexity. We also remove some heuristics on rounded Gaussians. Some of our results on rounded Gaussians might be of independent interest. Moreover, we also analyze algorithms solving LWE with discrete Gaussian noise.
Finally, we apply the same algorithm to the Learning With Rounding problem (LWR) for prime q, a deterministic counterpart to LWE. This problem is getting more and more attention and is used, for instance, to design pseudorandom functions. To the best of our knowledge, our algorithm is the first algorithm applied directly to LWR. Furthermore, the analysis of LWR contains some technical results of independent interest.
Category / Keywords: public-key cryptography / LWE, LWR, algorithm, BKW Original Publication (with minor differences): IACR-EUROCRYPT-2015 Date: received 23 Jan 2015, last revised 22 Apr 2015 Contact author: alexandre duc at epfl ch Available format(s): PDF | BibTeX Citation Version: 20150422:124055 (All versions of this report) Short URL: ia.cr/2015/056