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