Paper 2026/688

Too Far Behind? Narrowing the Gap with a Dual-Enhanced Two-Stage Algebraic Algorithm for LWE

Hong-Sen Yang, Information Engineering University, Zhengzhou 450001, China

Zhong-Xiao Wang, Information Engineering University, Zhengzhou 450001, China

Qun-Xiong Zheng, Information Engineering University, Zhengzhou 450001, China

Ye-Chen Li, Information Engineering University, Zhengzhou 450001, China

Abstract

The Learning with Errors (LWE) problem forms the foundation for numerous post-quantum cryptographic schemes, such as the NIST-selected CRYSTALS-KYBER and CRYSTALS-DILITHIUM. Algebraic analysis of LWE traditionally relies on solving the Arora-Ge system via Gröbner bases, yet its performance is far from satisfactory when only a limited number of samples is available. Meanwhile, recent dual attacks have proven highly effective against concrete LWE-based algorithms. This gap motivates us to investigate whether integrating techniques from dual attacks into algebraic analysis can have a positive effect. We propose a novel, two-stage algebraic algorithm for LWE. First, dual lattice reduction is applied to transform the original samples into lower-dimensional samples. From an algebraic perspective, this stage reduces the number of variables at the cost of increasing the noise. Second, instead of solving the classic Arora-Ge system, we introduce a new polynomial construction that exploits the error distribution and solves it via a resultant-based method. When given \(m = n\) samples, our two-stage algorithm yields better complexity estimates for CRYSTALS-KYBER than the Gröbner-basis estimates reported in Steiner's work (Eurocrypt~2024). As an independent contribution, we show that for LWE with a small secret, applying the resultant-based method directly to the Arora-Ge system provides a provable complexity estimate that achieves an exponential speed-up over the proven bounds established by Steiner. Finally, we show how various forms of side information---namely, perfect hints, modular hints, and approximate hints---can be systematically incorporated into our two-stage algorithm.

@misc{cryptoeprint:2026/688,
      author = {Rui-Jie Wang and Hong-Sen Yang and Zhong-Xiao Wang and Qun-Xiong Zheng and Ye-Chen Li},
      title = {Too Far Behind? Narrowing the Gap with a Dual-Enhanced Two-Stage Algebraic Algorithm for {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/688},
      year = {2026},
      url = {https://eprint.iacr.org/2026/688}
}