**Large Modulus Ring-LWE $\geq$ Module-LWE**

*Martin R. Albrecht and Amit Deo*

**Abstract: **We present a reduction from the module learning with errors problem (MLWE) in dimension \(d\) and with modulus \(q\) to the ring learning with errors problem (RLWE) with modulus \(q^{d}\). Our reduction increases the LWE error rate \(\alpha\) by a factor of \( n^{c+1/2} \cdot \sqrt{d} \) for ring dimension \(n\), module rank \(d\) and any constant \(c>0\) in the case of power-of-two cyclotomics. Since, on the other hand, MLWE is at least as hard as RLWE, we conclude that the two problems are polynomial-time equivalent. As a corollary, we obtain that the RLWE instance described above is equivalent to solving lattice problems on module lattices. We also present a self reduction for power-of-two cyclotomic RLWE that reduces the ring dimension \(n\) by a power-of-two factor \(2^i\), while increasing the modulus by a power of \(2^i\) and the error rate by a factor of \( 2^{i\cdot (1-c)} \cdot n^{c+1/2} \) for any constant \(c>0\). Our results suggest that when discussing hardness to drop the RLWE/MLWE distinction in favour of distinguishing problems by the module rank required to solve them.

**Category / Keywords: **public-key cryptography / security reduction, learning with errors, lattice-based cryptography

**Original Publication**** (with major differences): **IACR-ASIACRYPT-2017

**Date: **received 23 Jun 2017, last revised 11 Jan 2020

**Contact author: **amit deo 2015 at rhul ac uk

**Available format(s): **PDF | BibTeX Citation

**Note: **The analysis for our MLWE to MLWE reduction has been rewritten to allow for a smaller error rate expansion. The RLWE to RLWE dimension reducing reduction has been generalised using the recent work of Peikert and Pepin (TCC 2019). On a separate note, multiple mathematical typos carrying over from previous versions have been corrected -- we thank Katharina Boudgoust for finding these.

**Version: **20200111:121741 (All versions of this report)

**Short URL: **ia.cr/2017/612

[ Cryptology ePrint archive ]