### Algebraically Structured LWE, Revisited

Chris Peikert and Zachary Pepin

##### Abstract

In recent years, there has been a proliferation of algebraically structured Learning With Errors (LWE) variants, including Ring-LWE, Module-LWE, Polynomial-LWE, Order-LWE, and Middle-Product LWE, and a web of reductions to support their hardness, both among these problems themselves and from related worst-case problems on structured lattices. However, these reductions are often difficult to interpret and use, due to the complexity of their parameters and analysis, and most especially their (frequently large) blowup and distortion of the error distributions. In this paper we unify and simplify this line of work. First, we give a general framework that encompasses all proposed LWE variants (over commutative base rings), and in particular unifies all prior "algebraic" LWE variants defined over number fields. We then use this framework to give much simpler, more general, and tighter reductions from Ring-LWE to other algebraic LWE variants, including Module-LWE, Order-LWE, and Middle-Product LWE. In particular, all of our reductions have easy-to-analyze and frequently small error expansion; in some cases they even leave the error unchanged. A main message of our work is that it is straightforward to use the hardness of the original Ring-LWE problem as a foundation for the hardness of all other algebraic LWE problems defined over number fields, via simple and rather tight reductions.

Note: This version is a major update, containing additional definitions and more modular and general reductions.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2019
Keywords
Ring-LWEModule-LWEPolynomial-LWEOrder-LWEMiddle-Product LWE
Contact author(s)
cpeikert @ alum mit edu
zapepin @ umich edu
History
2020-11-01: last of 3 revisions
See all versions
Short URL
https://ia.cr/2019/878

CC BY

BibTeX

@misc{cryptoeprint:2019/878,
author = {Chris Peikert and Zachary Pepin},
title = {Algebraically Structured LWE, Revisited},
howpublished = {Cryptology ePrint Archive, Paper 2019/878},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/878}},
url = {https://eprint.iacr.org/2019/878}
}

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