Paper 2017/612
Large Modulus RingLWE $\geq$ ModuleLWE
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 poweroftwo cyclotomics. Since, on the other hand, MLWE is at least as hard as RLWE, we conclude that the two problems are polynomialtime 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 poweroftwo cyclotomic RLWE that reduces the ring dimension \(n\) by a poweroftwo factor \(2^i\), while increasing the modulus by a power of \(2^i\) and the error rate by a factor of \( 2^{i\cdot (1c)} \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.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 A major revision of an IACR publication in ASIACRYPT 2017
 Keywords
 security reductionlearning with errorslatticebased cryptography
 Contact author(s)
 amit deo 2015 @ rhul ac uk
 History
 20200111: last of 6 revisions
 20170626: received
 See all versions
 Short URL
 https://ia.cr/2017/612
 License

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} }