Better algorithms for LWE and LWR.

*(English)*Zbl 1365.94424
Oswald, Elisabeth (ed.) et al., Advances in cryptology – EUROCRYPT 2015. 34th annual international conference on the theory and applications of cryptographic techniques, Sofia, Bulgaria, April 26–30, 2015. Proceedings. Part I. Berlin: Springer (ISBN 978-3-662-46799-2/pbk; 978-3-662-46800-5/ebook). Lecture Notes in Computer Science 9056, 173-202 (2015).

Summary: 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 Blum-Kalai-Wasserman (BKW) algorithm was proposed by Blum et al. [J. ACM 50, No. 4, 506–519 (2003; Zbl 1325.68114)] as an algorithm to solve the Learning Parity with Noise problem (LPN), a subproblem of LWE. This algorithm was then adapted to LWE by M. R. Albrecht et al. [Des. Codes Cryptography 74, No. 2, 325–354 (2015; Zbl 1331.94051)].

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.

For the entire collection see [Zbl 1321.94010].

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.

For the entire collection see [Zbl 1321.94010].

##### MSC:

94A60 | Cryptography |