CryptoDB
On the Hardness of Module Learning with Errors with Short Distributions
| Authors: | |
|---|---|
| Download: | |
| Abstract: | The Module Learning With Errors ( $$\text {M-LWE}$$ 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 $$\text {M-LWE}$$ 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 toward narrowing this gap. More precisely, we prove that $$\text {M-LWE}$$ M-LWE with uniform $$\eta $$ η -bounded secret for any $$1 \le \eta \ll q$$ 1 ≤ η ≪ q and Gaussian error, in both its search and decision variants, is at least as hard as the standard formulation of $$\text {M-LWE}$$ 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 $$\text {M-LWE}$$ M-LWE with large uniform secret and uniform $$\eta $$ η -bounded error is at least as hard as the standard $$\text {M-LWE}$$ 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 $$\text {M-LWE}$$ M-LWE with uniform $$\eta $$ η -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. |
BibTeX
@article{jofc-2022-32779,
title={On the Hardness of Module Learning with Errors with Short Distributions},
journal={Journal of Cryptology},
publisher={Springer},
volume={36},
doi={10.1007/s00145-022-09441-3},
author={Katharina Boudgoust and Corentin Jeudy and Adeline Roux-Langlois and Weiqiang Wen},
year=2022
}