Paper 2019/930

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

Metadata
Available format(s)
PDF
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
2019-08-18: received
See all versions
Short URL
https://ia.cr/2019/930
License
Creative Commons Attribution
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.