Paper 2026/1400

What Happens When Integrating Modulus Switching and Lossy Source Coding: A New Dual Attack Variant on LWE

Abstract

The threat of large-scale quantum computers to classical public-key cryptograp-hy has motivated the development of post-quantum cryptographic schemes. Among these, lattice-based constructions have become the mainstream choice in the ongoing NIST standardization process. The security of these schemes typical-ly relies on the hardness of the LWE problem, and the dual-sieve-FFT attack is widely recognized as one of the most effective approaches against it. Recent improvements by MATZOV and Carrier et al. have significantly advanced its efficiency. In this paper, we propose a new variant of the dual-sieve-FFT attack that integrates modulus switching and lossy source coding. We provide a theoretical analysis of the integrated approach and show that the enumeration size in the FFT step can be reduced from 𝑞^𝑛_fft to 𝑝^𝑘_fft (with 𝑝 < 𝑞, 𝑘_fft < 𝑛_fft), leading to lower FFT cost and decoding cost. When applied to KYBER, our variant achieves better total complexity than the attack using only lossy source coding, although the improvement is modest. More importantly, the decoding and FFT costs are reduced by 1–6 bits and 2–7 bits, respectively, in most parame-ter settings. These reductions are practically meaningful, especially in multi-target attack scenarios where the FFT and decoding steps are amortized over multiple targets.