Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Abstract

We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies ${\hat{I}}^3\le 21<q/2=1664.5$ for ML-KEM-1024, with a success probability $\ge 0.99$. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(ζ_8)\subset\cdots\subset \Q(ζ_{2^k})$ which yields a polynomial-time quantum algorithm costing $O(n^3{\log }^{2}n)$ gates, $O(n^2\log n)$ qubits, and poly$(n)$ classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.

You have to read previous three parts (Parts I, II, III, arXiv:2604.15858, arXiv:2604.22900, arXiv:2605.17404) before understanding this part. I will upload simulations of main results (https://github.com/Postquantumcheck/Test/issues)