MLWE (and RLWE) to LWE reductions proof

Question

In crypto papers, cryptanalysis of MLWE/RLWE/etc. is often reduced to LWE. Why can we do this? Is there strict proof of such reductions?

Answer 1

There is no known reduction from LWE to MLWE (or to RLWE). That is, it could be that both MLWE and RLWE are broken, yet LWE is secure.

However, this seems highly unlikely. To support the security of LWE, we have reductions showing that breaking the average-case hardness of LWE requires breaking the worst-case hardness of some lattice problems - which would be (in the language of Brakerski et al.) "earth-shattering". Now, similar reductions hold for both MLWE and RLWE (see also this): both can be based on the worst-case hardness of lattice problems. The main difference is that RLWE requires worst-case hardness over ideal lattices, and MWLE requires worst-case hardness over module lattices.

Some notes about the above:

• everything strongly depends on the parameters. LWE-style assumptions are heavily parametrized, and saying "reduction" does not say much if we do not make explicit the parameters for which the reduction works. The reductions I mention above are for the most standard choices of parameters (e.g. polynomial modulus).
• Worst-case hardness over module lattices sounds more plausible than worst-case hardness over ideal lattices, for a variety of reasons. Yet, up to some important loss in the reduction, we actually do have reductions of RLWE to MLWE. This further illustrate while being precise with the parameter choices is important when discussing this topic.
• The main reason why cryptographers prefer using MLWE or RLWE over LWE is because they lead to much more efficient schemes. However, RLWE is parametrized by some polynomial, and requires hardness assumptions tailored to this very specific polynomial. This is a bit unsatisfying, because we don't really understand well the impact of the choice of polynomial on security. However, recently, a new problem was introduced, middle-product LWE. The latter gives us the best of both world: it allows essentially the same efficiency gains as standard RLWE or MLWE in many applications (see the paper, but also its follow-ups), yet it is as secure as RLWE with respect to any polynomial - hence to break it, you would need to break RLWE for every possible choice of the polynomial. This gives a very satisfying ground for the security of this assumption.

Answer 2

If I'm not wrong, in the LWE problem, you have less structure than in the RLWE/MLWE. If there is less structure, it means that the related problem is harder. Therefore an attack against LWE will work also against RLWE/MLWE. As far as I know, the interest of these variants is more about efficiency than security.