Paper 2022/1330

Hybrid Dual and Meet-LWE Attack

Lei Bi, Institute of Information Engineering, CAS
Xianhui Lu, Institute of Information Engineering, CAS
Junjie Luo, Beijing Jiaotong University
Kunpeng Wang, Institute of Information Engineering, CAS

The Learning with Errors (LWE) problem is one of the most prominent problems in lattice-based cryptography. Many practical LWE-based schemes, including Fully Homomorphic encryption (FHE), use sparse ternary secret for the sake of efficiency. Several (hybrid) attacks have been proposed that benefit from such sparseness, thus researchers believe the security of the schemes with sparse ternary secrets is not well-understood yet. Recently, May [Crypto 2021] proposed an efficient meet-in-the-middle attack named Meet-LWE for LWE with ternary se- cret, which significantly improves Odlyzko’s algorithm. In this work, we generalize May’s Meet-LWE and then introduce a new hybrid attack which combines Meet-LWE with lattice dual attack. We implement our algorithm to FHE-type parameters of LWE problem and compare it with the previous hybrid dual attacks. The result shows that our attack outperforms other attacks in a large range of parameters. We note that our attack has no impact on the LWE-based schemes in the PQC Standardization held by NIST as their secrets are not sparse and/or ternary.

Available format(s)
Attacks and cryptanalysis
Publication info
Published elsewhere. ACISP
LWEMeet-in-the-MiddleDual AttackHybrid Attack
Contact author(s)
bilei121 @ outlook com
luxianhui @ iie ac cn
jjluo1 @ bjtu edu cn
wangkunpeng @ iie ac cn
2022-12-23: last of 2 revisions
2022-10-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lei Bi and Xianhui Lu and Junjie Luo and Kunpeng Wang},
      title = {Hybrid Dual and Meet-LWE Attack},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1330},
      year = {2022},
      doi = {10.1007/978-3-031-22301-3_9},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.