3
$\begingroup$

I am trying to understand the NIST-submissions for post-quantum cryptography a bit better, and I noticed that the submissions from the CRYSTALS-family in particular is based on Module-LWE. I understand that "normal" LWE has huge parameters, and that they went for Ring-LWE in Ideal Lattices over Rings because of the more compact representation, as n samples require O(n) instead of O(n^2).

Though I fail to see what problem is solved by moving away from Ring-LWE towards Module-LWE, I assume that it provides better security? Is there some high-level intuition for me on what problem is solved exactly by letting security be based on Module-LWE instead of Ring-LWE? And how does this solves the problem?

$\endgroup$

4 Answers 4

1
$\begingroup$

My layman's understanding is as follows. Module-LWE is a generalization of Ring-LWE, i.e., if you can solve Module-LWE, then you can also solve Ring-LWE. More specifically, Ring-LWE is Module-LWE with a module of rank 1.

However, there is also a reduction in the opposite direction while assuming different modulus parameters - https://eprint.iacr.org/2017/612.pdf

AFAIK there is no definite proof that Module-LWE is strictly harder than Ring-LWE assuming same modulus (and other parameters) but it "seems like" that is the case? Bernstein goes in depth about this issue in https://ntruprime.cr.yp.to/latticerisks-20211031.pdf (specifically chapter 5)

This discussion in the pqc-forum is also interesting and might answer the question, specifically, Damien Stehlé's response https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/8_uKOBN4Srw/m/KoAbiE4TDAAJ

TLDR; Module-LWE is at least as hard as Ring-LWE assuming the same parameters, therefore, it is preferred to (more efficient) Ring-LWE because the cost difference is not "that big".

As I said, I am not expert on lattice cryptography so I hope I am not misinterpreting what I have read :`), feel free to correct me.

$\endgroup$
1
$\begingroup$

One reason is to have scalable security without having to change the underlying algebra; just increase the module dimension and work with the same base ring. E.g. Kyber can choose a small base ring with good-enough roots of unity for NTT and then scale the dimension to increase complexity/security.

Another reason is that the lattice is less structured, a free module over a smaller ring instead of a large ring.

Why use rings in the first place? Replacing some generic matrix multiplication (over a small base) with multiplication in a larger ring is more efficient (if perhaps more structured/less random).

MLWE is essentially "splitting the difference" between LWE and RLWE, a good working compromise (hopefully).

$\endgroup$
1
$\begingroup$

One reason I can see has nothing to do with security directly, but rather with the efficiency of running the algorithms and scaling them. If you want to increase the level of security in R-LWE, you have to increase the size of the polynomial. In M-LWE, you only need to increase the size of the matrices and the polynomials remain the same. This allows you to optimize the calculation of the polynomials for the specific size. You can also create custom hardware for that polynomial size. The matrices, on the other hand, are always the same calculations, just more of them when you have bigger ones. So just parallize them and they can run faster.

This makes it easier to adopt M-LWE and allows for better performance, especially with varying levels of security.

A better and longer explanation can be found here. Its already in teh Introduction: https://eprint.iacr.org/2023/895.pdf

$\endgroup$
1
  • $\begingroup$ Also, RLWE defined over non-power of two cyclotomic polynomials is cumbersome, thus, usually only RLWE "modulo" X^N + 1, with N being a power of two, is used. In this case, increasing the security means taking the next power of two, which can be an overkill (imagine N=2^12 almost gives you the desired security level, you would like to use something like N = 2^12 + 10, but instead, you have to use N=2^13). With modulo LWE, you can increase the dimension of the matrix by just the small constant you need to achieve the desired security level. $\endgroup$ Commented Apr 12 at 12:27
0
$\begingroup$

One can think of LWE systems such as Frodo and rLWE systems such as New Hope as instances of mLWE. Frodo's lattice is a module over the rational numbers which can be described as the cyclotomic field of degree 1; likewise New Hope is a rank 1 module over the large cyclotomic field.

In this sense all (r)LWE systems are MLWE systems.

The Crystals family seems to be planned around using the smallest cyclotomic field need to to achieve the bandwidth savings for $n$-samples and then using the rank of the module to make up the dimensions of the obvious lattice problem. Doing means that there is less symmetry in the obvious lattice as the rank of the module increases. On the other hand, there has not yet been a devastating use of the symmetry of the cyclotomic lattices to improve lattice attacks, so the concern about symmetry may be a paper tiger.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.