LaMS: A p-adic Layered Modulus Switching for Provable Dual Attacks on LWE

Rui-Jie Wang; Zhong-Xiao Wang; Qun-Xiong Zheng; Xuan Zhao

Paper 2026/1326

LaMS: A p-adic Layered Modulus Switching for Provable Dual Attacks on LWE

Rui-Jie Wang, Information Engineering University, Zhengzhou 450001, China

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

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

Xuan Zhao, Information Engineering University, Zhengzhou 450001, China

Abstract

The Learning with Errors (LWE) problem is a central foundation for post-quantum schemes such as Kyber and Dilithium. Dual attacks are among the main tools for assessing the concrete hardness of LWE instances. At EUROCRYPT 2024, Pouly and Shen introduced the first provable dual attack against LWE. Subsequently, at ASIACRYPT 2025, Qu and Xu incorporated modulus switching into this framework by recovering the guessed secret modulo several small primes and recombining the resulting residues via the Chinese Remainder Theorem (CRT). Although this CRT-based strategy substantially reduces the search space of each individual run, it reconstructs the full guessed secret through several distinct primes whose product must exceed $q$. Consequently, the total guessing cost is dominated by the largest CRT prime $p_k$. This raises a natural question: can the same recovery effect be achieved by repeatedly applying the subroutine with a fixed small prime, while further reducing the overall complexity? We answer this question affirmatively by proposing layered modulus switching ($\LaMS$), a provable modulus switching dual attack based on a $p$-adic view of the guessed secret. Instead of recovering residues modulo several distinct primes, \LaMS\ fixes a single small prime $p$ and recovers the guessed secret digit by digit in its $p$-adic expansion. After each digit is recovered, its contribution is subtracted from the LWE samples, producing a new target LWE instance in which the next digit becomes the new target modulo $p$. As a result, the dominant guessing term is reduced from $O(\nsol p_k^{\nsol})$ in the CRT-based attack to $O(\lceil \log_p q\rceil \nsol p^{\nsol})$, where $p < p_k$. We also correct a parameter issue in previous Kyber estimates. With this correction, \LaMS\ reduces the estimated attack cost by 22/31/41 bits for Kyber-512/768/1024, respectively, relative to the corrected CRT-based attack of Qu and Xu.

Note: We have updated the complexity estimation code on GitHub.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: LWE Provable dual attack Modulus switching CRT LaMS
Contact author(s): ruijie_wang1 @ 163 com
zhongxiao_wang @ 126 com
qunxiong_zheng @ 163 com
xuanzhao5280 @ outlook com
History: 2026-07-01: revised; 2026-06-26: received; See all versions
Short URL: https://ia.cr/2026/1326
License: CC BY

BibTeX

@misc{cryptoeprint:2026/1326,
      author = {Rui-Jie Wang and Zhong-Xiao Wang and Qun-Xiong Zheng and Xuan Zhao},
      title = {{LaMS}: A p-adic Layered Modulus Switching for Provable Dual Attacks on {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/1326},
      year = {2026},
      url = {https://eprint.iacr.org/2026/1326}
}