Cryptology ePrint Archive: Report 2019/878

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 our reductions have easy-to-analyze effects on the error, and 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 reductions.

Category / Keywords: foundations / Ring-LWE, Module-LWE, Polynomial-LWE, Order-LWE, Middle-Product LWE

Date: received 30 Jul 2019

Contact author: cpeikert at alum mit edu,zapepin@umich edu

Available format(s): PDF | BibTeX Citation

Version: 20190801:132319 (All versions of this report)

Short URL: ia.cr/2019/878


[ Cryptology ePrint archive ]