On the Hardness of Module Learning with Errors with Short Distributions

Katharina Boudgoust (1) , Corentin Jeudy (2, 3) , Adeline Roux-Langlois (4) , Weiqiang Wen (5, 6, 7)

1 Aarhus University [Aarhus]
2 Orange Labs [Cesson-Sévigné]
3 CAPSULE - Applied Cryptography and Implementation Security
4 Equipe AMACC - Laboratoire GREYC - UMR6072
5 IP Paris - Institut Polytechnique de Paris
6 INFRES - Département Informatique et Réseaux
7 C2 - Cybersécurité et Cryptographie

The Module Learning With Errors (M-LWE) problem 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 uniform $\eta$-bounded secret for any $1 \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 search M-LWE with uniform η-bounded secret and error under specific parameter conditions. Overall, the results apply to all cyclotomic fields, but most of the intermediate results are proven in more general number fields.

Keywords: Lattice-Based Cryptography; Module Learning With Errors; Short Distributions; Bounded Secret; Bounded Error

Domains: Cryptography and Security [cs.CR]

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, Weiqiang Wen. On the Hardness of Module Learning with Errors with Short Distributions. Journal of Cryptology, 2023, 36 (1), pp.1-72. ⟨10.1007/s00145-022-09441-3⟩. ⟨hal-04028217⟩