Large Modulus Ring-LWE and Module-LWE

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 $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 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 $\mathbf{a}, \mathbf{s} \in \mathbb{Z}_{q}^{d}$ with $\mathbf{s}$ small it holds that

$q^{d-1} \cdot \langle{\mathbf{a},\mathbf{s}}\rangle \approx \left(\sum_{i=0}^{d-1} q^{i} \cdot a_{i}\right) \cdot \left(\sum_{i=0}^{d-1} q^{d-i-1} \cdot s_{i}\right) \bmod q^{d} = \tilde{a} \cdot \tilde{s} \bmod q^{d}.$

Thus, if there exists an efficient algorithm solving the problem in $\mathbb{Z}_{q^d}$ , we can use it to solve the problem in $\mathbb{Z}_{q}^d$ .

In our paper, we essentially show that we can replace integers mod $q$ resp. $q^d$ with the ring of integers $R$ of a Cyclotomic field (considered mod $q$ resp. $q^d$ ). That is, we get the analogous reduction from $R_{q}^d$ (MLWE) to $R_{q^d}$ (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 $R$ rather than $\mathbb{Z}$ .

Continue reading “Large Modulus Ring-LWE and Module-LWE” →

A Generator for LWE and Ring-LWE Instances

We’re ready to announce our LWE/Ring-LWE generators for Sage:

We introduce software for the generation of instances of the LWE and Ring-LWE problems, allowing both the generation of generic instances and also particular instances closely-related to those arising from cryptomania proposals in the literature. Our goal is to allow researchers to attack different instances in order to assess the practical hardness of LWE and Ring-LWE. This will in turn give insight to the practical security of cryptographic systems based on both problems.

IACR Announcement, interactive demo.

Ring-LWE and the GB(N) Problem

Over at the Bristol Cryptography Blog Martijn Stam writes about our “Polly Cracker, Revisted” paper:

We did not discuss the paper in great detail, but Jake did mention one interesting avenue for continued research. Given that this new approach allows one to cast both LWE and approximate GCD in the same framework, can one also capture ring-LWE. If so, this might enable a better comparison of the various fully homomorphic encryption (FHE) schemes out there. The hope expressed by Jake was that this might allow a reduction to standard LWE (for the current batch of ring-LWE schemes), which would boost our confidence in those schemes.

This motivated me to express the Ring-LWE problem in a language of Gröbner bases, here’s what I could come up with so far. Continue reading “Ring-LWE and the GB(N) Problem” →