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 cryptography 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 typically 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 $q^{n_\text{fft}}$ to $p^{k_\text{fft}}$ (with $p <q, k_{\text{fft}} < n_{\text{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 parameter settings. These reductions are practically meaningful in scenarios where memory usage or multi-target attacks are of concern.