## 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 quadratic factor in the ring dimension $n$ and a square root in the module rank $d$ for 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 \emph{module} lattices. We also present a self reduction for RLWE in power-of-two cyclotomic rings that halves the dimension and squares the modulus while increasing the error rate by a similar factor as our MLWE to RLWE reduction. 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 minor differences): IACR-ASIACRYPT-2017

Date: received 23 Jun 2017, last revised 14 Nov 2017

Contact author: amit deo 2015 at rhul ac uk

Available format(s): PDF | BibTeX Citation

Note: Full version of ASIACRYPT 2017 paper.

Short URL: ia.cr/2017/612

[ Cryptology ePrint archive ]