Score:2

Why Module-LWE and not Ring-LWE?

kz flag

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 this solves the problem?

Score:1
in flag

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).

Score:0
ru flag

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.

Score:0
cn flag

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.

I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.