Paper 2022/472

On the Hardness of Module Learning With Errors with Short Distributions

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 $$ 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 $$-bounded secret for any $$ 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 $$ is at least logarithmic in the ring degree $$. We also prove that the search version of M-LWE with large uniform secret and uniform $$-bounded error is at least as hard as the standard M-LWE problem, if the number of samples $$ is close to the module rank $$ and with further restrictions on $$. The latter result can be extended to provide the hardness of 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.

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)