### 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.

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.

Available format(s)
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in Asiacrypt 2017
Keywords
security reductionlearning with errorslattice-based cryptography
Contact author(s)
amit deo 2015 @ rhul ac uk
History
2020-01-11: last of 6 revisions
See all versions
Short URL
https://ia.cr/2017/612

CC BY

BibTeX

@misc{cryptoeprint:2017/612,
author = {Martin R.  Albrecht and Amit Deo},
title = {Large Modulus Ring-LWE $\geq$ Module-LWE},
howpublished = {Cryptology ePrint Archive, Paper 2017/612},
year = {2017},
note = {\url{https://eprint.iacr.org/2017/612}},
url = {https://eprint.iacr.org/2017/612}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.