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

2026/05/17 by Ming-Xing Luo · 1 voice
Computer Science · Mathematics · Physics and Astronomy · #cs.CR #math.CO #math.RA #quant-ph

paper · pdf · doi:10.48550/arxiv.2605.17412

arxiv published 2026/05/17 · arxiv updated 2026/05/25

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 γ≤ 21 < q/2=1664.5 for ML-KEM-1024, with a success probability ≥ 0.99. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain \Q⊂ \Q(ζ₈)⊂⋯⊂ \Q(ζ_2^k) which yields a polynomial-time quantum algorithm costing O(n³ log² n) gates, O(n² 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.

Citations

• Predicting Module-Lattice Reduction
• Lattice sieving via quantum random walks
• Worst-case to average-case reductions for module lattices
• Surface codes: Towards practical large-scale quantum computation
• Quantum Computation and Quantum Information
• Faster arithmetic for number-theoretic transforms
• The Solovay-Kitaev algorithm
• Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions
• Topological quantum memory
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• A hierarchy of polynomial time lattice basis reduction algorithms
• Minkowski's Convex Body Theorem and Integer Programming
• Factoring polynomials with rational coefficients
• A method for obtaining digital signatures and public-key cryptosystems

Discussions

• Polynomial Quantum Attack on Module-LWE over Power-of-2 Cyclotomics [hn, 1 points, 0 comments]

Related

• Some Mathematical Problems Behind Lattice-Based Cryptography
• Quantum Algorithm for Optimization and Polynomial System Solving over Finite Field and Application to Cryptanalysis
• Provably weak instances of Ring-LWE
• Post-Quantum Key Agreement Protocol based on Non-Square Integer Matrices
• Quantum Period Finding against Symmetric Primitives in Practice