Common Notation

Truncated LWE implied

Propose Edit

Updated:

Truncated (Module-)LWE was first defined by Boudgoust and Keller in 2025 [1]. The assumption truncates the lower-order bits of the LWE challenge matrix \(\mat{A}\) to optimise storage, computation, and bandwidth. They note that Truncated MLWE can be seen as a special case of (Module-)LWE with semiuniform distribution [2].

Definition

Truncated LWE\(_{\mathcal{R},n,m,q,\chi_s,\chi_e,c}\)

Let \(\chi_s\) and \(\chi_e\) be distributions over \(\mathcal{R}\). Let \(\mathsf{Trunc}(\cdot, c)\) denote the operation of deleting the \(c\) lowest-order bits of each coefficient. Sample \(\bar{\mat{A}} \sample \mathcal{R}_q^{m \times n}\), \(\vec{s} \sample \chi_s^n\), \(\vec{e} \sample \chi_e^m\), and \(\vec{b} \sample \mathcal{R}_q^m\). Obtain \(\mat{A} \leftarrow \mathsf{Trunc}(\bar{\mat{A}}, c)\). An adversary is asked to distinguish between the distribution

\[(\mat{A}, \mat{A} \vec{s} + \vec{e}) \text{ and } (\mat{A}, \vec{b}).\]

We define module-version of Truncated LWE given in [1]. If \(c=0\) then we recover Module-LWE and if \(\mathcal{R} = \ZZ\), we recover LWE.

Hardness

Jia et al. [2] give a reduction from the module-variant of NTRU to the search variant of Truncated MLWE (with entropic secret).

Boudgoust and Keller [1] provide reductions from Module-LWE and Hint-MLWE:

  • In Theorem 2, they reduce Search-MLWE to the search version of Truncated MLWE using Rénji divergence. This reduction is vacuous in certain contexts, as the Rényi divergence between truncated and non-truncated matrices is exponentially large in their dimensions.
  • In Theorem 3, they reduce Hint-MLWE to Truncated LWE for both, search and decision, variants of the problems.

Constructions built from Truncated LWE

None explicitly.

References

  • [1]Katharina Boudgoust and Hannah Keller. 2025. Module Learning with Errors with Truncated Matrices. In Post-Quantum Cryptography - 16th International Workshop, PQCrypto 2025, Taipei, Taiwan, April 8-10, 2025, Proceedings, Part I (Lecture Notes in Computer Science), 2025. Springer, 255–277. Retrieved from https://ia.cr/2025/120
  • [2]Wenjuan Jia, Jiang Zhang, and Baocang Wang. 2023. Hardness of Module-LWE with Semiuniform Seeds from Module-NTRU. IET Inf. Secur. 2023, (2023), 1–16. https://doi.org/10.1049/2023/2969432