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

Ming-Xing Luo · 2026

Read Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics by Ming-Xing Luo (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-17412.txt.

Introduction

Luo claims a polynomial-time quantum attack on ML-KEM and related lattice schemes over two-power cyclotomic rings. A tower breakdown of the principal ideal problem through cyclotomic fields yields an algorithm with cubic-log gate cost and quadratic-log qubit cost, plus polynomial classical work. For ML-KEM-1024 he reports an approximation factor at most 21, well under half the modulus, with success probability at least 99 percent. The analysis extends to Falcon, Hawk and NTRU.

Catalog record

CREATORMing-Xing Luo
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66318
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.17412

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics Ming-Xing Luo 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 \gamma\leq 21<q/2=1664.5 for ML-KEM-1024, with a success probability ≥ 0.99 \geq 0.99 . We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain ℚ ⊂ ℚ ⁡ ( ζ 8 ) ⊂ ⋯ ⊂ ℚ ⁡ ( ζ 2 k ) \mathbb{Q}\subset\mathbb{Q}(\zeta_{8})\subset\cdots\subset\mathbb{Q}(\zeta_{2^{k}}) which yields a polynomial-time quantum algorithm costing O ⁡ ( n 3 ​ log 2 ​ n ) O(n^{3}\log^{2}n) gates, O ⁡ ( n 2 ​ log ⁡ n ) O(n^{2}\log n) qubits, and poly ( n ) (n) classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms. Keywords: Quantum attack, cyclotomic tower, probabilistic polynomial quantum algorithm, log-unit lattice, Babai’s algorithm, post-quantum cryptography. 1 Introduction The global transition to post-quantum cryptography is a great challenge for modern information security. Once large-scale fault-tolerant quantum computers are realized, Shor’s algorithm [ 1 ] can break all classical public-key schemes based on integer factorization [ 2 ] and discrete logarithms [ 3 ] . In response, NIST completed a standardization process [ 4 ] and selected ML-KEM (originally CRYSTALS-Kyber [ 5 ] ) as the primary federal standard for post-quantum key encapsulation [ 6 ] . ML-KEM’s security reduces to the hardness of Module Learning With Errors (Module-LWE) [ 7 ] , which in turn benefits from worst-case to average-case reductions from the Module Shortest Vector Problem [ 7 , 8 ] . The most direct quantum cryptanalytic route is the CDPR algorithm [ 9 ] , which exploits the algebraic structure of cyclotomic rings to find short generators of principal ideals. However, there are two critical open questions that have remained open: 1. Is the CDPR approximation factor sufficiently small for full ML-KEM secret-key recovery? 2. Does the underlying quantum PIP subroutine achieve true polynomial-time complexity, with no hidden exponential overhead and generalize Riemann hypothesis? This part answers both questions affirmatively. We summaries each part’s key contribution as: • Part I. Proves h_{k}^{+}=1 (trivial class number) for the maximal real subfield of \mathbb{Q}(\zeta_{2^{k}}) for every k\leq 12 , giving the ring a PID-like structure that makes every ideal principal. • Part II. Proves that the module-to-ideal reduction introduces only a constant factor \alpha_{d}=O(1) independent of module rank d . • Part III. Computes the exact L^{2} CVP constant \pi/(2\sqrt{6}) for the log-unit lattice, shows the nearest lattice point is always the origin for short generators, and proves the per-component variance \sigma_{g_{0}}=O(1) regardless of the modulus q . • Part IV (this paper). Shows four parts combined can imply a probabilistic quantum algorithm costing O(n^{3}\log^{2}n) gates, and \gamma\leq 21<q/2 for ML-KEM-1024, with 99% \gamma\approx 103 below threshold, and extend to analyze Falcon, Hawk, and NTRU over 2-power cyclotomics. The rest is organized as follows. Section 2 shows preliminaries. Section 3 contributes the full pipeline including all main algorithms. Section 4 answers whether the resulting approximation factor \gamma is small enough to break ML-KEM. Section 5 shows polynomial tower PIP algorithm which gives the first polynomial-time construction. Section 6 extends the analysis to other lattice schemes including Falcon, Hawk, and NTRU over 2-power cyclotomics. Section 7 compares the present result with known results while the last section concludes the paper. 2 Preliminaries This section introduces some definitions, notation, and background results that are used in the rest of the paper. 2.1 Cyclotomic rings Let m=2^{k} , n=2^{k-1}=m/2 , and \zeta=e^{2\pi\mathrm{i}/m} . The 2^{k} -th cyclotomic ring is defined by R=\mathbb{Z}[\zeta] , the ring of integers of the cyclotomic field K=\mathbb{Q}(\zeta) [ 10 , 11 ] . The Galois group \Gal(K/\mathbb{Q})\cong(\mathbb{Z}/m\mathbb{Z})^{\times} consists of all automorphisms \sigma_{a}:\zeta\mapsto\zeta^{a} for odd integers a\in\{1,3,\dots,m-1\} [ 10 ] . The canonical embeddings are defined by \sigma_{j}:K\hookrightarrow\mathbb{C} with \sigma_{j}(g)=\sum_{i}c_{i}\zeta^{ij} , for odd j\in\{1,3,\dots,m-1\} . These evaluate the polynomial g at the n distinct primitive m -th roots of unity. There are n/2 independent embeddings. The field norm of g\in K is defined by \Nm_{K/\mathbb{Q}}(g)=\prod_{j\text{ odd}}\sigma_{j}(g)\in\mathbb{Z} , and the trace is \Tr_{K/\mathbb{Q}}(g)=\sum_{j\text{ odd}}\sigma_{j}(g)\in\mathbb{Z} . Both are integers for any g\in R [ 11 , 12 ] . For a unit \varepsilon\in R^{\times} , we have |\Nm(\varepsilon)|=1 . 2.2 Module lattices A lattice \Lambda\subset\mathbb{R}^{m} is a discrete additive subgroup, equivalently the set of all integer linear combinations of a basis \{\mathbf{b}_{1},\dots,\mathbf{b}_{r}\}\subset\mathbb{R}^{m} [ 13 ] . The minimum distance is defined by \lambda_{1}(\Lambda)=\min_{\mathbf{v}\in\Lambda\setminus\{0\}}\|\mathbf{v}\|_{2} , i.e., the length of the shortest nonzero vector. Finding \lambda_{1} is the Shortest Vector Problem (SVP), which is the central hard problem underlying lattice-based cryptography. A module lattice arises from a free R -module M\cong R^{d} embedded into Euclidean space via the canonical embeddings [ 14 , 7 ] . A rank- d module lattice over R is determined by a matrix B\in R^{d\times d} as \displaystyle\Lambda_{B}=\{B\mathbf{z}:\mathbf{z}\in R^{d}\}\subset K^{d}. (1) Applying the embeddings \sigma_{j} entry-wise to every element of K^{d} changes this into a classical Euclidean lattice of \mathbb{Z} -rank nd , in \mathbb{R}^{nd} . The secret key of ML-KEM [ 6 ] is a short vector (\mathbf{s}_{1},\mathbf{s}_{2})\in R^{k}\times R^{\ell} lying in a coset of the module lattice \displaystyle\Lambda_{A}=\{(\mathbf{z}_{1},\mathbf{z}_{2})\in R^{\ell}\times R^{k}:A\mathbf{z}_{1}+\mathbf{z}_{2}\equiv\mathbf{0}\pmod{q}\}. (2) Recovering (\mathbf{s}_{1},\mathbf{s}_{2}) from the public key (A,\mathbf{t}) with \mathbf{t}=A\mathbf{s}_{1}+\mathbf{s}_{2} is SVP on this module lattice. The hardness of this problem is shown by Langlois and Stehlé [ 7 ] . 2.3 Hardness assumptions and attack target This subsection explains the two security assumptions underlying the NIST standards. Module-LWE (Hardness assumption). The module learning with errors problem [ 15 , 14 , 7 ] asserts that, given \mathbf{A}\in R_{q}^{k\times\ell} uniformly at random and \mathbf{t}=A\mathbf{s}_{1}+\mathbf{s}_{2}+\mathbf{e}\pmod{q} for short secret and error vectors, it is computationally infeasible to recover (\mathbf{s}_{1},\mathbf{s}_{2},\mathbf{e}) even with a quantum computer. This assumption is the foundation of ML-KEM’s security proof. Module-SVP (Target). This paper attacks the approximate Module-SVP: find a vector \mathbf{v} in the module lattice \Lambda with \|\mathbf{v}\|\leq\gamma\dot{\lambda}_{1}(\Lambda) , for the smallest achievable approximation factor \gamma . If \gamma<q/2 (for ML-KEM) or \gamma<q/\beta (for ML-DSA), the vector \mathbf{v} recovers the secret key. Generic lattice reduction algorithms including LLL [ 16 ] , BKZ [ 17 , 18 ] , and lattice sieving [ 19 , 20 ] do not exploit the cyclotomic ring structure. Their best approximation factors for ML-KEM-1024 are about 2^{220} , which is larger than the security threshold. The CDPR attack [ 9 ] achieves an exponentially gate count because it solves a completely different easier problem: the Principal Ideal Problem (PIP), which is polynomial-time on a quantum computer when the ring has trivial class number. 2.4 The log-embedding Definition 2.1 . For a non-zero element g\in K , the log-embedding is defined by \displaystyle L(g)=\bigl(\log|\sigma_{j}(g)|\bigr)_{\text{odd }j\in[1,m)}\in\mathbb{R}^{n}. (3) The trace-zero projection can remove the overall scale as \displaystyle\Pi_{H_{0}}(L(g))=L(g)-\frac{1}{n}\log|\Nm_{K/\mathbb{Q}}(g)|\cdot{}\mathbf{1}\in H_{0}, (4) where H_{0}=\{x\in\mathbb{R}^{n}:\sum_{j}x_{j}=0\} is the trace-zero hyperplane. The log-unit lattice is defined by \Lambda=\{L(\epsilon):\epsilon\in R^{\times}\}\subset H_{0} . From the Dirichlet’s Unit Theorem [ 11 ] (with r_{1}=0 , r_{2}=n/2 for complex field K ), \Lambda has rank r=n/2-1 . The log-unit lattice encodes the

Read the complete text