Welcome to the resource topic for 2019/930
Title:
Module-LWE versus Ring-LWE, Revisited
Authors: Yang Wang, 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.
ePrint: https://eprint.iacr.org/2019/930
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .