Paper 2025/120

Module Learning with Errors with Truncated Matrices

Katharina Boudgoust, CNRS, Univ Montpellier, LIRMM
Hannah Keller, Aarhus University
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.