On the Hardness of Module-LWE with Binary Secret
Co-authored with Katharina Boudgoust, Adeline Roux-Langlois, and Weiqiang Wen.
In the proceedings of CT-RSA 2021. Also available on IACR ePrint.
Abstract
We prove that the Module Learning With Errors (M-LWE) problem with binary secrets and rank
is at least as hard as the standard version of M-LWE with uniform secret and rank , where the rank increases from to , and the Gaussian noise from to , where is the ring degree and the modulus. Our work improves on the recent work by Boudgoust et al. in 2020 by a factor of in the Gaussian noise, where is the number of given M-LWE samples, when fulfills some number-theoretic requirements. We use a different approach than Boudgoust et al. to achieve this hardness result by adapting the previous work from Brakerski et al. in 2013 for the Learning With Errors problem to the module setting. The proof applies to cyclotomic fields, but most results hold for a larger class of number fields, and may be of independent interest.