Welcome to the resource topic for 2017/612
Title:
Large Modulus Ring-LWE \geq Module-LWE
Authors: Martin R. Albrecht, 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 power-of-two cyclotomics. Since, on the other hand, MLWE is at least as hard as RLWE, we conclude that the two problems are polynomial-time 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 power-of-two cyclotomic RLWE that reduces the ring dimension (n) by a power-of-two factor (2^i), while increasing the modulus by a power of (2^i) and the error rate by a factor of ( 2^{i\cdot (1-c)} \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.
ePrint: https://eprint.iacr.org/2017/612
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 .