Paper 2021/265
On the Hardness of ModuleLWE with Binary Secret
Katharina Boudgoust, Corentin Jeudy, Adeline RouxLanglois, and Weiqiang Wen
Abstract
We prove that the Module Learning With Errors (MLWE) problem with binary secrets and rank $d$ is at least as hard as the standard version of MLWE with uniform secret and rank $k$, where the rank increases from $k$ to $d \geq (k+1)\log_2 q + \omega(\log_2 n)$, and the Gaussian noise from $\alpha$ to $\beta = \alpha \cdot \Theta(n^2\sqrt{d})$, where $n$ is the ring degree and $q$ the modulus. Our work improves on the recent work by Boudgoust et al. in 2020 by a factor of $\sqrt{md}$ in the Gaussian noise, where $m$ is the number of given MLWE samples, when $q$ fulfills some numbertheoretic 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.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. CTRSA 2021
 Keywords
 Latticebased cryptographymodule learning with errorsbinary secret
 Contact author(s)
 katharina boudgoust @ irisa fr
 History
 20210303: received
 Short URL
 https://ia.cr/2021/265
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/265, author = {Katharina Boudgoust and Corentin Jeudy and Adeline RouxLanglois and Weiqiang Wen}, title = {On the Hardness of Module{LWE} with Binary Secret}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/265}, year = {2021}, url = {https://eprint.iacr.org/2021/265} }