Paper 2017/612

Large Modulus Ring-LWE $\ge$ 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 $$ for any constant $$. 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.

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.