Paper 2015/056

Better Algorithms for LWE and LWR

Alexandre Duc, Florian Tramèr, and Serge Vaudenay

Abstract

The Learning With Error problem (LWE) is becoming more and more used in cryptography, for instance, in the design of some fully homomorphic encryption schemes. It is thus of primordial importance to find the best algorithms that might solve this problem so that concrete parameters can be proposed. The BKW algorithm was proposed by Blum et al. as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by Albrecht et al. 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in EUROCRYPT 2015
Keywords
LWELWRalgorithmBKW
Contact author(s)
alexandre duc @ epfl ch
History
2015-04-22: revised
2015-01-23: received
See all versions
Short URL
https://ia.cr/2015/056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/056,
      author = {Alexandre Duc and Florian Tramèr and Serge Vaudenay},
      title = {Better Algorithms for LWE and LWR},
      howpublished = {Cryptology ePrint Archive, Paper 2015/056},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/056}},
      url = {https://eprint.iacr.org/2015/056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.