Paper 2019/878

Algebraically Structured LWE, Revisited

Chris Peikert, University of Michigan–Ann Arbor
Zachary Pepin, University of Michigan–Ann Arbor
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 most 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 generalizes the definitions and results significantly.

Metadata
Available format(s)
PDF
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
2023-06-09: last of 4 revisions
2019-08-01: received
See all versions
Short URL
https://ia.cr/2019/878
License
Creative Commons Attribution
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.