Paper 2021/265

On the Hardness of Module-LWE with Binary Secret

Katharina Boudgoust, Corentin Jeudy, Adeline Roux-Langlois, and Weiqiang Wen

Abstract

We prove that the Module Learning With Errors (M-LWE) problem with binary secrets and rank $d$ is at least as hard as the standard version of M-LWE 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 M-LWE samples, when $q$ 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision.CT-RSA 2021
Keywords
Lattice-based cryptographymodule learning with errorsbinary secret
Contact author(s)
katharina boudgoust @ irisa fr
History
2021-03-03: received
Short URL
https://ia.cr/2021/265
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/265,
      author = {Katharina Boudgoust and Corentin Jeudy and Adeline Roux-Langlois and Weiqiang Wen},
      title = {On the Hardness of Module-LWE with Binary Secret},
      howpublished = {Cryptology ePrint Archive, Paper 2021/265},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/265}},
      url = {https://eprint.iacr.org/2021/265}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.