Paper 2025/120
Module Learning with Errors with Truncated Matrices
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. PQCrypto 2025
- Keywords
- LatticesModule Learning with ErrorsTruncation
- Contact author(s)
-
katharina boudgoust @ lirmm fr
hkeller @ cs au dk - History
- 2025-01-27: approved
- 2025-01-26: received
- See all versions
- Short URL
- https://ia.cr/2025/120
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/120, author = {Katharina Boudgoust and Hannah Keller}, title = {Module Learning with Errors with Truncated Matrices}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/120}, year = {2025}, url = {https://eprint.iacr.org/2025/120} }