Paper 2021/1358

The Hardness of LWE and Ring-LWE: A Survey

David Balbás

Abstract

The Learning with Errors (LWE) problem consists of distinguishing linear equations with noise from uniformly sampled values. LWE enjoys a hardness reduction from worst-case lattice problems, which are believed to be hard for classical and quantum computers. Besides, LWE allows for the construction of a large variety of cryptographic schemes, including fully-homomorphic encryption and attribute-based cryptosystems. Unfortunately, LWE requires large key sizes and computation times. To improve efficiency, Ring-LWE replaces linear equations with noisy ring products. Nowadays, Ring-LWE and its variants are frequently used in the construction of post-quantum secure cryptosystems. In this survey, we give an overview of the hardness results for LWE and Ring-LWE, aiming to connect both problems and to provide good intuition to the reader. We present a proof of the strongest hardness result for Ring-LWE available the literature, which is a reduction from ideal lattice problems to its decision form. We start by introducing both Ring-LWE and LWE and their mathematical foundations, focusing on lattices and algebraic number theory. Then, we sketch the classical hardness proof for LWE and extend the proof techniques to the ring case. We also introduce informal discussions on parameter choices, weaknesses, related work, and open problems.