Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics
This work claims to break several NIST-standardized post-quantum cryptosystems, which if correct, would have enormous impact on cryptographic security.
The authors present a polynomial-time quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes, achieving an approximation factor γ ≤ 21 < q/2 = 1665 for ML-KEM-1024 with success probability ≥ 0.99, thereby breaking all standardized parameter sets of ML-KEM, Falcon, Hawk, and NTRU under quantum attack.
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 $γ\le 21 < q/2=1665$ 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 $\mathrm{poly}(n)$ classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings. This means that ML-KEM, Falcon, Hawk, NTRU-HPS, and NTRU-HRSS with all standardized parameter sets are broken under quantum attack.