Paper 2026/1060

An Improved Hybrid Dual Attack on LWE with Sparse Secrets and its Application to FHE

, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Yijian Liu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Xianhui Lu, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Junjie Luo, School of Mathematics and Statistics, Beijing Jiaotong University

Kunpeng Wang, Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Abstract

The Learning with Errors (LWE) problem serves as a cornerstone of modern cryptography, underlying advanced schemes such as Fully Homomorphic Encryption (FHE). Many FHE schemes adopt LWE instances with sparse ternary secrets, leaving them vulnerable to attacks. In 2022, Bi-Lu-Luo-Wang [ACISP 2022] proposed a hybrid dual attack that combines May's Meet-in-the-Middle (MITM) algorithm [Crypto 2021] with a dual attack and shows that it outperforms other attacks in a large range of FHE-type parameters. However, their attack suffers from two main efficiency bottlenecks: the costly enumeration of error entries and the large number of hash function labels. In this work, we conduct a systematic analysis of several variants of May's MITM algorithm equipped with different list constructions and hash functions. Based on this, we propose a new hybrid dual attack that incorporates the most efficient variant, effectively mitigating both bottlenecks. We further enhance the attack by adopting a better hypothesis testing algorithm for FHE settings. Addressing recent concerns raised by Ducas-Pulles [Crypto 2023] regarding the independence heuristic in dual attacks, we provide a rigorous theoretical and empirical analysis. We demonstrate that, for typical FHE parameters, our attack does not rely on the problematic independence heuristic and lies outside the contradictory regime. Finally, we compare our attack with previous hybrid attacks, showing consistent and significant improvements across all evaluated cases. In particular, our results invalidate the accelerated BGV scheme in [EUROCRYPT 2024] by reducing its bit-security below the claimed security level, with the most extreme case being 18 bits lower.

@misc{cryptoeprint:2026/1060,
      author = {Lei Bi and Yijian Liu and Xianhui Lu and Junjie Luo and Kunpeng Wang},
      title = {An Improved Hybrid Dual Attack on {LWE} with Sparse Secrets and its Application to {FHE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1060},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1060}
}