Welcome to the resource topic for 2025/120
Title:
Module Learning with Errors with Truncated Matrices
Authors: Katharina Boudgoust, Hannah Keller
Abstract:The Module Learning with Errors (\mathsf{MLWE}) problem is one of the most commonly used hardness assumption in lattice-based cryptography. In its standard version, a matrix \mathbf{A} is sampled uniformly at random over a quotient ring R_q, as well as noisy linear equations in the form of \mathbf{A} \mathbf{s}+ \mathbf{e} \bmod q, where \mathbf{s} is the secret, sampled uniformly at random over R_q, and \mathbf{e} is the error, coming from a Gaussian distribution. Many previous works have focused on variants of \mathsf{MLWE}, where the secret and/or the error are sampled from different distributions. Only few works have focused on different distributions for the matrix \mathbf{A}. One variant proposed in the literature is to consider matrix distributions where the low-order bits of a uniform \mathbf{A} are deleted. This seems a natural approach in order to save in bandwidth. We call it truncated \mathsf{MLWE}.
In this work, we show that the hardness of standard \mathsf{MLWE} implies the hardness of truncated \mathsf{MLWE}, both for search and decision versions. Prior works only covered the search variant and relied on the (module) \mathsf{NTRU} assumption, limitations which we are able to overcome. Overall, we provide two approaches, offering different advantages. The first uses a general Rényi divergence argument, applicable to a wide range of secret/error distributions, but which only works for the search variants of (truncated) \mathsf{MLWE}. The second applies to the decision versions, by going through an intermediate variant of \mathsf{MLWE}, where additional hints on the secret are given to the adversary. However, the reduction makes use of discrete Gaussian distributions.
ePrint: https://eprint.iacr.org/2025/120
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .