Paper 2022/472

On the Hardness of Module Learning With Errors with Short Distributions

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, and Weiqiang Wen

Abstract

The Module Learning With Errors problem (M-LWE) is a core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency. The problem is parameterized by a secret distribution as well as an error distribution. There is a gap between the choices of those distributions for theoretical hardness results (standard formulation of M-LWE, i.e., uniform secret modulo $q$ and Gaussian error) and practical schemes (small bounded secret and error). In this work, we make progress towards narrowing this gap. More precisely, we prove that M-LWE with $\eta$-bounded secret for any $2 \leq \eta \ll q$ and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of M-LWE, provided that the module rank $d$ is at least logarithmic in the ring degree $n$. We also prove that the search version of M-LWE with large uniform secret and uniform $\eta$-bounded error is at least as hard as the standard M-LWE problem, if the number of samples $m$ is close to the module rank $d$ and with further restrictions on $\eta$. The latter result can be extended to provide the hardness of M-LWE with uniform $\eta$-bounded secret and error under specific parameter conditions.

Note: This paper contains novel results and generalizations of existing ones already published in Boudgoust et al. (Asiacrypt'20) and Boudgoust et al. (CT-RSA'21)

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
Lattice-Based CryptographyModule Learning With ErrorsShort DistributionsBounded SecretBounded Error
Contact author(s)
corentin jeudy @ irisa fr
History
2022-04-22: received
Short URL
https://ia.cr/2022/472
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/472,
      author = {Katharina Boudgoust and Corentin Jeudy and Adeline Roux-Langlois and Weiqiang Wen},
      title = {On the Hardness of Module Learning With Errors with Short Distributions},
      howpublished = {Cryptology ePrint Archive, Paper 2022/472},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/472}},
      url = {https://eprint.iacr.org/2022/472}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.