## Cryptology ePrint Archive: Report 2017/612

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.

Short URL: ia.cr/2017/612

[ Cryptology ePrint archive ]