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}$ .

Interpretation

Since the Module-LWE problem has been suggested (e.g. here) to hedge against algebraic attacks on Ring-LWE, a natural question is how to interpret this reduction. One might be tempted to conclude that the suggestion is simply wrong. That is, looked at in abstraction from the size of the modulus (for a constant error rate $\alpha$ ), Module-LWE seems no more secure than Ring-LWE and thus a poor hedging strategy.

However, this abstraction from the size of the modulus is misleading (hat tip to our anonymous referees and Léo Ducas). If there exists an efficient algorithm that solves Ring-LWE for a fixed error rate $\alpha$ but any modulus, then this algorithm can also be used solve any LWE instance. This was already remarked in the Classical Hardness paper and we give a sketch in Appendix B of our paper: convert LWE to a 1-dimensional instance with exponential modulus and then construct an RLWE instance from this 1-dimensional instance. Such an adversary might exist, i.e. we cannot in principle rule out that LWE might be easy, but it will not be an adversary exploiting the special algebraic structure of Ring-LWE since LWE has none of that.

Furthermore, consider the dual attack on plain LWE using a set of samples $\{(\mathbf{a}_i, c_i) : i = 0, \ldots, {m-1} \}$ . In order to perform this attack, a short vector $\mathbf{y}$ in the $m$ -dimensional dual lattice to the lattice formed by the $\mathbf{a}_{i}$ must be found. This dual lattice has volume $q^n$ whp. Using the Gaussian heuristic, the shortest vector in such a lattice is expected to have length $\approx q^{n/m}$ . The attack proceeds by noticing that the inner-product $\langle{ \mathbf{y}, \mathbf{c} }\rangle = \langle{ \mathbf{y}, \mathbf{e} }\rangle$ should be small in the case of LWE samples and uniform otherwise. In particular, the smaller $\langle{ \mathbf{y}, \mathbf{e} }\rangle$ , the more certain we are that the samples were in fact from an LWE distribution. Concretely, for a fixed error rate $\alpha$ , we have $\langle{ \mathbf{y}, \mathbf{c} }\rangle \approx \alpha\, q^{n/m}$ in the case where the modulus is $q$ . On the other hand, if the modulus is $q^2$ , we expect $\langle{\mathbf{y}, \mathbf{c}}\rangle \approx \alpha\, q^{2n/m}$ which is larger for fixed $\alpha, n, m$ . Therefore, the performance of the dual attack diminishes for growing $q$ . Indeed, our output RLWE instance in modulus $q^d$ has noise of size at least $q^{d/2}$ . Thus, our RLWE output instances cannot be solved by finding short vectors in lattices of module rank 2 ( $m=2n$ in the above notation) using standard dual attacks in contrast to typical RLWE instances used in the literature. In other words: “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.”

Public-Key Encryption from Large Modulus RLWE

As alluded to above, large modulus RLWE instances are not very popular in cryptographic constructions. A reason for this is that they tend not to work very well in those constructions. Recall, for example, the simple public-key encryption scheme from the original RLWE paper which serves as the blueprint for many subsequent constructions. The scheme publishes a public-key $(a,b = a\cdot s + e)$ , where both $s$ and $e$ are small elements from the ring of integers of a power-of-two Cyclotomic field. Encryption of some polynomial $m$ with $\{0,1\}$ coefficients is then performed by sampling short $r,e_{1},e_{2}$ and outputting:

$\big(u,\, v\big) = \big(a\cdot r + e_{1},\quad b\cdot r + e_{2} + \lfloor q/2 \rfloor \cdot m \bmod q\big).$

The decryption algorithm computes

$u\cdot s - v = (a\cdot r + e_{1})\cdot s - (a \cdot s + e) \cdot r - e_{2} - \lfloor q/2 \rfloor \cdot m = e_{1}\cdot s - e \cdot r - e_{2} - \lfloor q/2 \rfloor \cdot m.$

Let $\sigma$ be the norm of $s,e, r,e_{1},e_{2}$ . Clearly, the final message will have noise of norm $\geq \sigma^{2}$ . Thus, to ensure correct decryption, $q$ has a quadratic dependency on $\sigma$ . As a consequence, in this construction, increasing $\sigma$ and $q$ can only reduce security by increasing the gap between noise and modulus.

However, this issue can be avoided (and is avoided when basing the construction on the MLWE assumption) by picking some $\sigma' < \sigma$ at the cost of publishing more samples in the public key. For example, if $d=2$ the public key becomes

$\left((a',b'),\, (a'',b'') \right) = \left((a', a'\cdot s + e'),\, (a'', a''\cdot s + e'')\right),$

where $s,e'e,''$ have norm $\sigma$ . Encryption of some $\{0,1\}$ polynomial $m$ is then performed by sampling short $r',r'',e_{1},\,e_{2}$ with norm $\sigma'$ and outputting

$\left(u,\, v\right) = \left(a'\cdot r' + a''\cdot r'' + e_{1},\quad b'\cdot r' + b''\cdot r'' + e_{2} + \lfloor q/2 \rfloor \cdot m \bmod q\right).$

The decryption algorithm computes

$u\cdot s - v = (a'\cdot r' + a''\cdot r'' + e_{1})\cdot s - (a'\cdot s + e')\cdot r' - (a''\cdot s + e'')\cdot r'' - e_{2} - \lfloor q/2 \rfloor \cdot m.$

The security of the public key reduces to the hardness of RLWE in dimension $n$ with modulus $q$ and noise size $\sigma$ as before. The security of encryptions reduces to the hardness of MLWE in dimension $d=2$ over ring dimension $n$ , modulus $q$ and noise size $\sigma'$ , i.e. the level of security is maintained for $\sigma' < \sigma$ by increasing the dimension. While we still require $q > \sigma \cdot \sigma'$ , the size of $\sigma'$ can be reduced at the cost of increasing $d$ .

Finally, we may think of Regev’s original encryption scheme as one extreme corner of this design space (for LWE) with $d=2\,n \log q$ , where $r',r'',\ldots$ are binary and where $e_{1},e_{2},\ldots=0,0,\ldots$ . That is, in the construction above, we can replace the Module-LWE assumption by the leftover hash lemma if $d$ is sufficiently big. Of course, this comes at the cost of a significant increase in the size of the public key. On the other hand, we would now only require $q > \sigma \cdot \sqrt{2\,n \log q}$ .

Interpretation

Public-Key Encryption from Large Modulus RLWE

Share this:

Like this:

Related

Leave a Reply Cancel reply