Our paper Large Modulus Ring-LWE ≥ Module-LWE — together with Amit Deo — was accepted at AsiaCrypt 2017. Here’s the abstract:
We present a reduction from the module learning with errors problem (MLWE) in dimension
and with modulus
to the ring learning with errors problem (RLWE) with modulus
. Our reduction increases the LWE error rate
by a quadratic factor in the ring dimension
and a square root in the module rank
for 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 RLWE in power-of-two cyclotomic rings that halves the dimension and squares the modulus while increasing the error rate by a similar factor as our MLWE to RLWE reduction. 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.
Our reduction is an application of the main result from Classical Hardness of Learning with Errors in the context of MLWE. In its simplest form, that reduction proceeds from the observation that for with
small it holds that
Thus, if there exists an efficient algorithm solving the problem in , we can use it to solve the problem in
.
In our paper, we essentially show that we can replace integers mod resp.
with the ring of integers
of a Cyclotomic field (considered mod
resp.
). That is, we get the analogous reduction from
(MLWE) to
(RLWE). The bulk of our paper is concerned with making sure that the resulting error distribution is sound. This part differs from the Classical Hardness paper since our target distribution is in
rather than
.