TY - GEN
T1 - On the Hardness of Module-LWE with Binary Secret
AU - Boudgoust, Katharina
AU - Jeudy, Corentin
AU - Roux-Langlois, Adeline
AU - Wen, Weiqiang
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021/1/1
Y1 - 2021/1/1
N2 - 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≥ (k+ 1 ) log 2q+ ω(log 2n), and the Gaussian noise from α to β=α·Θ(n2d), 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 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.
AB - 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≥ (k+ 1 ) log 2q+ ω(log 2n), and the Gaussian noise from α to β=α·Θ(n2d), 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 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.
KW - Binary secret
KW - Lattice-based cryptography
KW - Module learning with errors
U2 - 10.1007/978-3-030-75539-3_21
DO - 10.1007/978-3-030-75539-3_21
M3 - Conference contribution
AN - SCOPUS:85111007868
SN - 9783030755386
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 503
EP - 526
BT - Topics in Cryptology-CT-RSA 2021 - Cryptographers’ Track at the RSA Conference, Proceedings
A2 - Paterson, Kenneth G.
PB - Springer Science and Business Media Deutschland GmbH
T2 - Cryptographer's Track at the RSA Conference, CT-RSA 2021
Y2 - 17 May 2021 through 20 May 2021
ER -