TY - GEN
T1 - Towards Classical Hardness of Module-LWE
T2 - 26th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2020
AU - Boudgoust, Katharina
AU - Jeudy, Corentin
AU - Roux-Langlois, Adeline
AU - Wen, Weiqiang
N1 - Publisher Copyright:
© 2020, International Association for Cryptologic Research.
PY - 2020/1/1
Y1 - 2020/1/1
N2 - We prove that the module learning with errors (M - LWE ) problem with arbitrary polynomial-sized modulus p is classically at least as hard as standard worst-case lattice problems, as long as the module rank d is not smaller than the number field degree n. Previous publications only showed the hardness under quantum reductions. We achieve this result in an analogous manner as in the case of the learning with errors (LWE ) problem. First, we show the classical hardness of M - LWE with an exponential-sized modulus. In a second step, we prove the hardness of M - LWE using a binary secret. And finally, we provide a modulus reduction technique. The complete result applies to the class of power-of-two cyclotomic fields. However, several tools hold for more general classes of number fields and may be of independent interest.
AB - We prove that the module learning with errors (M - LWE ) problem with arbitrary polynomial-sized modulus p is classically at least as hard as standard worst-case lattice problems, as long as the module rank d is not smaller than the number field degree n. Previous publications only showed the hardness under quantum reductions. We achieve this result in an analogous manner as in the case of the learning with errors (LWE ) problem. First, we show the classical hardness of M - LWE with an exponential-sized modulus. In a second step, we prove the hardness of M - LWE using a binary secret. And finally, we provide a modulus reduction technique. The complete result applies to the class of power-of-two cyclotomic fields. However, several tools hold for more general classes of number fields and may be of independent interest.
KW - Binary secret
KW - Classical hardness
KW - Lattice-based cryptography
KW - Module learning with errors
UR - https://www.scopus.com/pages/publications/85097831946
U2 - 10.1007/978-3-030-64834-3_10
DO - 10.1007/978-3-030-64834-3_10
M3 - Conference contribution
AN - SCOPUS:85097831946
SN - 9783030648336
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 289
EP - 317
BT - Advances in Cryptology – ASIACRYPT 2020 - 26th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Moriai, Shiho
A2 - Wang, Huaxiong
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 7 December 2020 through 11 December 2020
ER -