Paper 2019/878

Algebraically Structured LWE, Revisited

Chris Peikert and Zachary Pepin


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)
Publication info
A major revision of an IACR publication in TCC 2019
Ring-LWEModule-LWEPolynomial-LWEOrder-LWEMiddle-Product LWE
Contact author(s)
cpeikert @ alum mit edu
zapepin @ umich edu
2020-11-01: last of 3 revisions
2019-08-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Chris Peikert and Zachary Pepin},
      title = {Algebraically Structured LWE, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2019/878},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.