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 $\gamma \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 $\text{Q}\subset \text{Q}({\zeta }_8)\subset \cdots \subset \text{Q}({\zeta }_{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.