Paper 2017/612
Large Modulus Ring-LWE >= Module-LWE
Martin R. Albrecht and 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 quadratic factor in the ring dimension \(n\) and a square root in the module rank \(d\) 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 \emph{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.
Note: Full version of ASIACRYPT 2017 paper.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2017
- Keywords
- security reductionlearning with errorslattice-based cryptography
- Contact author(s)
- amit deo 2015 @ rhul ac uk
- History
- 2020-01-11: last of 6 revisions
- 2017-06-26: received
- See all versions
- Short URL
- https://ia.cr/2017/612
- License
-
CC BY