Module Learning with Errors with Truncated Matrices

Katharina Boudgoust, Hannah Keller

TL;DR

This paper proves that the hardness of the standard Module Learning with Errors (MLWE) problem implies the hardness of a "truncated" variant of MLWE. This is a significant step towards understanding the security of lattice-based cryptography, as it shows that a practical optimization (truncating matrix bits to save bandwidth) doesn't inherently weaken the underlying cryptographic assumptions. The authors achieve this through two novel reduction techniques, one using Rényi divergence and another employing a "hinted" MLWE variant.

What Problem Does This Paper Address?

The Module Learning with Errors (MLWE) problem is a cornerstone of modern lattice-based cryptography, forming the basis for many secure schemes. In MLWE, an adversary is given a matrix $A$ and a noisy linear equation $b = As + e$, where $s$ is a secret vector and $e$ is an error term. The adversary's goal is to recover $s$ (search variant) or distinguish a true MLWE sample from random data (decision variant).

While the standard MLWE problem assumes $A$ is sampled uniformly at random, practical implementations often need to reduce the size of cryptographic keys and ciphertexts. One way to do this is by "truncating" the matrix $A$, meaning its low-order bits are discarded. This saves bandwidth but raises a crucial question: does this truncation weaken the underlying security assumption? Previous work had only shown reductions for specific variants or assumptions, leaving the general case open. This paper directly addresses this gap by proving that the hardness of standard MLWE does imply the hardness of this truncated MLWE problem, for both search and decision variants.

Methods

The authors present two main approaches to prove their results:

  1. Rényi Divergence Approach: This method leverages the concept of Rényi divergence, a measure of how "different" two probability distributions are. The core idea is to view a truncated matrix $A$ as a uniform matrix $U$ minus its low-order bits ($N_U$). A truncated MLWE sample $(A, As+e)$ can then be reinterpreted as a standard MLWE sample $(U, Us+e')$, where the new error $e'$ is related to the original error $e$ and the truncated bits $N_U$. By carefully analyzing the Rényi divergence between the original error distribution and the new error distribution $e'$, they show that if the original MLWE is hard, the truncated version is also hard. This approach is flexible regarding the secret and error distributions but is primarily applicable to the search variant.
  2. MLWE with Hints Approach: This method introduces an intermediate problem called "MLWE with Hints." In this variant, an adversary not only receives the standard MLWE input $(A, b)$ but also some "hints" about the secret $s$. The authors show that the hardness of MLWE with hints can be reduced from standard MLWE. They then demonstrate that truncated MLWE can be reduced to MLWE with hints, where the hints are precisely the low-order bits of the matrix $A$. This approach works for both search and decision variants but requires specific properties for the error and noise distributions (like discrete Gaussians).

Datasets

Not discussed in the paper. The paper focuses on theoretical hardness reductions rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Truncation is (provably) safe: The most significant insight is the formal proof that truncating the low-order bits of the MLWE matrix does not compromise the underlying security assumption. This is crucial for practical cryptographic implementations.
  • Rényi divergence as a powerful tool: The paper showcases the continued utility of Rényi divergence for proving tight security reductions in lattice cryptography, demonstrating its flexibility for various distributions.
  • Bridging search and decision variants: The second approach, using MLWE with hints, is particularly important as it provides a unified way to prove hardness for both search and decision variants of truncated MLWE.
  • Decomposition of matrices: The core idea of viewing a truncated matrix as a uniform matrix minus its low-order bits provides a clean mathematical framework for the reductions.

Key Results

The paper establishes the following key results:

  • Theorem 2: The hardness of standard MLWE implies the hardness of truncated MLWE for the search variant, using Rényi divergence. This reduction is flexible regarding secret and error distributions, provided they satisfy certain bounds and Rényi divergence properties.
  • Theorem 3: The hardness of standard MLWE implies the hardness of truncated MLWE for both search and decision variants, by reducing through an intermediate "MLWE with Hints" problem. This approach requires specific distributions, such as discrete Gaussians.
  • Corollaries: The paper provides concrete instantiations of these theorems for common distributions like uniform, rounded Gaussian, and discrete Gaussian, showing how the hardness of truncated MLWE relates to standard MLWE under these specific conditions.

Limitations and Future Work

  • Ring Restrictions: The results are primarily proven for power-of-two cyclotomic rings. While the authors mention that generalization to other fields and rings is possible, it might incur looser norm bounds due to expansion factors.
  • Distributional Constraints: The Rényi divergence approach is flexible but limited to search variants. The MLWE with hints approach, while covering decision variants, relies on specific distributional properties (e.g., discrete Gaussians) and can increase the "width" of these distributions.
  • Trivial Setup Avoidance: The authors explicitly note that their reductions avoid a trivial setup where the truncated MLWE problem becomes easily solvable. This is achieved by ensuring the resulting error distribution is sufficiently large.
  • Future Directions: The paper suggests exploring a unified approach that captures both additive (like truncation) and multiplicative decompositions of matrices, potentially leading to more general results. They also highlight the importance of understanding the trade-offs between different reduction approaches concerning parameters like ring degree and dimension.

Summary updated

Abstract

The Module Learning with Errors (\(\textsf{MLWE}\)) problem is one of the most commonly used hardness assumption in lattice-based cryptography. In its standard version, a matrix \(\textbf{A}\) is sampled uniformly at random over a quotient ring \(R_q\), as well as noisy linear equations in the form of \(\textbf{A}\textbf{s}+ \textbf{e}\bmod q\), where \(\textbf{s}\) is the secret, sampled uniformly at random over \(R_q\), and \(\textbf{e}\) is the error, coming from a Gaussian distribution. Many previous works have focused on variants of \(\textsf{MLWE}\), where the secret and/or the error are sampled from different distributions. Only few works have focused on different distributions for the matrix \(\textbf{A}\). One variant proposed in the literature is to consider matrix distributions, where the low-order bits of a uniform \(\textbf{A}\) are deleted. This seems a natural approach in order to save in bandwidth. We call it truncated \(\textsf{MLWE}\).
BibTeX
@article{boudgoust2025module,
  author = {Katharina Boudgoust and Hannah Keller},
  title = {{Module Learning with Errors with Truncated Matrices}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2025},
}
Figure