### Module-LWE versus Ring-LWE, Revisited

Yang Wang and Mingqiang Wang

##### Abstract

Till now, the only reduction from the module learning with errors problem (MLWE) to the ring learning with errors problem (RLWE) is given by Albrecht $et\ al.$ in ASIACRYPT $2017$. Reductions from search MLWE to search RLWE were satisfactory over power-of-$2$ cyclotomic fields with relative small increase of errors. However, a direct reduction from decision MLWE to decision RLWE leads to a super-polynomial increase of errors and does not work even in the most special cases-\ -power-of-$2$ cyclotomic fields. Whether we could reduce decision MLWE to decision RLWE and whether similar reductions could also work for general fields are still open. In this paper, we give a reduction from decision MLWE with module rank $d$ and computation modulus $q$ in worst-case to decision RLWE with modulus $q^d$ in average-case over any cyclotomic field. Our reduction increases the LWE error rate by a small polynomial factor. As a conclusion, we obtain an efficient reduction from decision MLWE with modulus $q\approx\tilde{O}(n^{5.75})$ and error rate $\alpha\approx\tilde{O}(n^{-4.25})$ in worst-case to decision RLWE with error rate $\Gamma\approx\tilde{O}(n^{-\frac{1}{2}})$ in average-case, hence, we get a reduction from worst-case module approximate shortest independent vectors problem (SIVP$_\gamma$) with approximation parameter $\gamma\approx\tilde{O}(n^{5})$ to corresponding average-case decision RLWE problems. Meanwhile, our result shows that the search variant reductions of Albrecht $et\ al.$ could work in arbitrary cyclotomic field as well. We also give an efficient self-reduction of RLWE problems and a converse reduction from decision MLWE to module SIVP$_{\gamma}$ over any cyclotomic field as improvements of relative results showed by Rosca $et\ al.$ in EUROCRYPT $2018$ and Langlois $et\ al.$ $[\rm{DCC}\ 15]$. Our methods can also be applied to more general algebraic fields $K$, as long as we can find a good enough basis of the dual $R^{\vee}$ of the ring of integers of $K$.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
Lattice-based CryptographySecurity ReductionCyclotomic FieldsRing-LWEModule-LWE
Contact author(s)
wyang1114 @ mail sdu edu cn
wangmingqiang @ sdu edu cn
History
2020-05-30: revised
See all versions
Short URL
https://ia.cr/2019/930

CC BY

BibTeX

@misc{cryptoeprint:2019/930,
author = {Yang Wang and Mingqiang Wang},
title = {Module-LWE versus Ring-LWE, Revisited},
howpublished = {Cryptology ePrint Archive, Paper 2019/930},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/930}},
url = {https://eprint.iacr.org/2019/930}
}

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