### 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.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
learning with errorsring learning with errorslatticeslattice-based cryptographypost-quantum cryptography
Contact author(s)
david balbas @ imdea org
History
Short URL
https://ia.cr/2021/1358

CC BY

BibTeX

@misc{cryptoeprint:2021/1358,
author = {David Balbás},
title = {The Hardness of LWE and Ring-LWE: A Survey},
howpublished = {Cryptology ePrint Archive, Paper 2021/1358},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1358}},
url = {https://eprint.iacr.org/2021/1358}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.