Module Lattice Security (Part IV):
Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics
May 17, 2026
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 \(\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)\) 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.
Keywords: Quantum attack, cyclotomic tower, probabilistic polynomial quantum algorithm, log-unit lattice, Babai’s algorithm, post-quantum cryptography.
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:
Is the CDPR approximation factor sufficiently small for full ML-KEM secret-key recovery?
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\le 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\le 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.
This section introduces some definitions, notation, and background results that are used in the rest of the paper.
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 \(\mathop{\mathrm{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_ic_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 \(\mathop{\mathrm{N}}_{K/\mathbb{Q}}(g)=\prod_{j \text{ odd}} \sigma_j(g)\in \mathbb{Z}\), and the trace is \(\mathop{\mathrm{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 \(|\mathop{\mathrm{N}}(\varepsilon)|=1\).
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 [7], [14]. A rank-\(d\) module lattice over \(R\) is determined by a matrix \(B\in R^{d \times d}\) as \[\begin{align} \Lambda_B=\{B\mathbf{z}: \mathbf{z}\in R^d\} \subset K^d. \label{Elangm} \end{align}\tag{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 \[\begin{align} \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\}. \label{Elmabda} \end{align}\tag{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].
This subsection explains the two security assumptions underlying the NIST standards.
Module-LWE (Hardness assumption). The module learning with errors problem [7], [14], [15] 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}\|\le \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.
Definition 1. For a non-zero element \(g\in K\), the log-embedding is defined by \[\begin{align} L(g)=\bigl(\log|\sigma_j(g)|\bigr)_{\text{odd } j\in [1,m)}\in \mathbb{R}^n. \label{eqlogn} \end{align}\tag{3}\] The trace-zero projection can remove the overall scale as \[\begin{align} \Pi_{H_0}(L(g))=L(g)-\frac{1}{n}\log|\mathop{\mathrm{N}}_{K/\mathbb{Q}}(g)|\cdot{}\mathbf{1}\in H_0, \label{eqproj} \end{align}\tag{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 unit group \(R^\times\) as a Euclidean lattice, converting the multiplicative problem of finding a short unit into the additive problem of CVP.
Definition 2. For a nonzero \(g\in K\), the log-embedding is given by \[\begin{align} L(g)=(\log|\sigma_1(g)|, \log|\sigma_3(g)|, \dots, \log|\sigma_{n-1}(g)|)\in \mathbb{R}^{n/2}. \label{eqLg} \end{align}\tag{5}\] As each conjugate embeddings has equal modulus, we denote one representative from each pair and then obtain a vector in \(\mathbb{R}^{n/2}\).
The trace-zero hyperplane \(H_0=\{x\in \mathbb{R}^{n/2:} \sum_i x_i=0\}\) contains all log-embedded units as \(\sum_j\log|\sigma_j(\varepsilon)|=\log|\mathop{\mathrm{N}}(\varepsilon)|=0\) for \(\varepsilon\in R^\times\).
Definition 3. For log-unit lattice \(\Lambda=L(R^\times) \subset H_0\), when \(h_k^+=1\), a basis for \(\Lambda\) can be represented as the log-embeddings of the cyclotomic units \(\xi_a=\sin(a\pi/m)/\sin(\pi/m)\) for odd \(a\in \{1, 3, \dots, n-1\}\) [10], [21].
Every unit \(\varepsilon\in R^\times\) maps to a point \(L(\varepsilon)\) in \(\Lambda\). Two generators of the same ideal are different by a unit, i.e., if \((g_0)=(g)\), then \(g=g_0 \varepsilon\) for some \(\varepsilon\in R^\times\). So, we have \(L(g)=L(g_0)+L(\varepsilon)\).
Definition 4. The Short Generator Problem (SGP) is defined by: Given a principal ideal \(I=(g)\subset R\) with a long generator \(g\) (potentially of exponentially large norm), find a short generator \(g_0\) such that \((g_0)=I\) and \(\lVert g_0\rVert_2\) is small.
Since \(g=g_0\varepsilon\), we have \(\Pi_{H_0}(L(g))=\Pi_{H_0}(L(g_0))+L(\varepsilon)\), where \(\Pi_{H_0}\) denotes orthogonal projection onto \(H_0\). The problem of solving SGP is then reduced to CVP on \(\Lambda\): The CVP solution \(L(\varepsilon)\in\Lambda\) identifies the unit discrepancy, and then \(g_0=g\cdot{}\varepsilon^{-1}\).
Babai’s nearest-plane algorithm [18], [22] is the specific CVP algorithm used in Phase 2 of the CDPR attack [9]. For a general lattice and target, it provides only an approximation to the nearest lattice point.
Given a lattice basis \(B=(\mathbf{b}_1, \dots, \mathbf{b}_r)\) with Gram-Schmidt orthogonalization (GSO) \(B^* =(\mathbf{b}_1^*, \dots, \mathbf{b}_r^*)\) [18], and a target \(\mathbf{t}\), Babai’s nearest-plane algorithm rounds the projection coefficients from \(i=r\) to \(i=1\) as \[\begin{align} c_i=\left\lfloor\frac{\langle\mathbf{t}-\sum_{j>i} c_j \mathbf{b}_j,\, \mathbf{b}_i^* \rangle}{\|\mathbf{b}_i^*\|^2}\right\rceil. \label{eqBabai} \end{align}\tag{6}\] The output lattice vector is defined by \(\mathbf{v}=\sum_i c_i\mathbf{b}_i\) and the residual is \(\boldsymbol{\rho}=\mathbf{t}-\mathbf{v}\).
The Coarse Lattice Theorem (Part III) shows that for the specific targets arising from short ring generators, all rounding coefficients \(c_i\) equal zero, so Babai’s algorithm outputs the zero vector and the residual is the target itself. The Infinite Capture Radius Theorem (Part III) then shows that Babai’s algorithm can exactly recover an arbitrary lattice translation of such a target.
The Module Learning With Errors (MLWE) problem over \(R\) with rank \(d\), modulus \(q\), and error distribution \(\chi\) asks to distinguish between samples \((A, A\mathbf{s}+\mathbf{e})\) and \((A, \mathbf{u})\), where \(A\in R_q^{d \times d}\), \(\mathbf{s, e}\in R_q^d\) are small, and \(\mathbf{u}\) is uniform.
ML-KEM’s security can be reduced to MLWE, which in turn reduced to Module-SVP with an approximation factor \(\gamma\) [7], [23]. An attacker who finds a vector of norm at most \(\gamma\cdot{}\lambda_1(\Lambda_q)\) in module lattice can distinguish MLWE samples [7], [15]. For full secret-key recovery, the attacker needs \(\gamma < q/2\), i.e., the recovered vector should have coordinates small enough to be uniquely decoded modulo \(q\) by bounded-distance decoding [9], [24], see Table 1.
| Scheme | \(d\) | \(n\) | \(q\) | Attack threshold \(q/2\) |
|---|---|---|---|---|
| ML-KEM-512 | 2 | 256 | 3329 | 1664.5 |
| ML-KEM-768 | 3 | 256 | 3329 | 1664.5 |
| ML-KEM-1024 | 4 | 256 | 3329 | 1664.5 |
This section presents the full attack as a single Algorithm.
The extended CDPR attack proceeds in four phases: Module to ideal reduction, Quantum PIP, Log-unit CVP and Short generator. The important stage is to factor \(g=g_0 \varepsilon\): the quantum phase finds some generator \(g\) of the ideal, but \(g\) may be exponentially larger than the shortest generator \(g_0\). The classical phases recover the unit \(\varepsilon\) and divide it out.
The approximation factor \(\gamma\) is the key quantity connecting the lattice attack to the cryptographic security of ML-KEM. Especially, our approximation factor is given by \[\begin{align} \gamma=\lVert g_0\rVert/\|g_{\rm short}\|=\exp(\|\boldsymbol{\rho}\|_\infty), \label{eqapprx} \end{align}\tag{7}\] where \(\boldsymbol{\rho}\) is the CVP residual. Parts II and III together show that \(\|\boldsymbol{\rho}\|_\infty=O(\sqrt{\log n})\), which implies \(\gamma=\exp(O(\sqrt{\log n})) \ll n^\epsilon\) for every \(\epsilon > 0\). For ML-KEM-1024 with \(n=256\), this evaluates to \(\gamma_{\rm th} \approx 21\) at the median and \(\gamma_{99\%} \approx 103\), both far below the threshold \(q/2=1664.5\).
All symbols used in what follows are shown in Table 2. Here, note the difference between \(\sigma_j\) (an embedding of \(K\)) and \(\sigma_d\) (the intrinsic log-unit imbalance of the module determinant ideal), and between \(\boldsymbol{\rho}\) (the CVP residual vector) and \(\psi'\) (the trigamma function).
| Symbol | Meaning |
|---|---|
| \(k \ge 3\) | Tower level index |
| \(m=2^k\) | Conductor |
| \(n=2^{k-1}\) | Ring degree \(= [K:\mathbb{Q}]\) |
| \(\zeta=e^{2\pi\mathrm{i}/m}\) | Primitive \(m\)-th root of unity |
| \(R=\mathbb{Z}[\zeta]\) | Cyclotomic ring of integers |
| \(K=\mathbb{Q}(\zeta)\) | Cyclotomic field |
| \(\sigma_j\) | Canonical embedding (\(j\) odd, \(1\le j\le m-1\)) |
| \(J=\{1,3,\dots,n-1\}\) | Representatives of conjugate pairs |
| \(\Lambda\) | Log-unit lattice (rank \(r=n/2-1\)) |
| \(H_0\) | Trace-zero hyperplane in \(\mathbb{R}^{n/2}\) |
| \(\Pi_{H_0}\) | Orthogonal projection onto \(H_0\) |
| \(\psi'\) | Trigamma function |
| \(\boldsymbol{\rho}\) | CVP residual vector |
| \(\gamma\) | SGP approximation factor \(= \exp(\|\boldsymbol{\rho}\|_\infty)\) |
This subsection present the main algorithm shown in Algorithm [alg:ecdpr] for the extended CDPR attack.
Extended CDPR Attack on ML-KEMalg:ecdpr
INPUTS: \(B\in R^{d \times d}\): a module basis matrix for a rank-\(d\) Module-LWE instance over \(R=\mathbb{Z}[\zeta_{2^k}]\) \(q\): the ML-KEM modulus (e.g., \(q=3329\) for ML-KEM-1024) \(k\le 12\): the tower level (\(h_k^+=1\) by Part I)
OUTPUT: A short generator \(g_0\in R\) of the determinant ideal \((\det B) \subset R\), with approximation factor \(\gamma=\exp(\|\boldsymbol{\rho}\|_\infty) < q/2\)
PHASE 1: Module-to-Ideal Reduction (Part II) Compute the Gram-Schmidt decomposition: \(B=Q_R\cdot{}T_R\), where \(T_R\in R^{d \times d}\) is upper triangular with principal ideals \(I_i=(T_{R,ii}) \subset R\) on the diagonal. Set the determinant ideal \(I=I_1\cdot{}I_2\cdots I_d=(\det B) \subset R\).
PHASE 2: Quantum Tower PIP (Section 5) Recall the cyclotomic tower: \(\mathbb{Q}\subset K_3 \subset K_4 \subset\cdots \subset K_k=K\). for \(L=3, 4, \dots, k\) do ) Compute the norm ideal \(J_L=\mathop{\mathrm{N}}_{K_L/K_L^+}(I_L) \subset R_L^+\), \(I_L=I \cap R_L\). ) Set up an abelian HSP for the relative extension \(K_L^+/K_{L-1}^+\): Group: \(G_L=(\mathbb{Z}/N_L\mathbb{Z})^{\Delta r_L}\), \(N_L=2^{O(L\cdot{}2^L)}\), \(\Delta r_L=2^{L-3}\) new unit generators at level \(L\). Oracle: \(f_L(e_1,\dots,e_{\Delta r_L})= \prod_a \xi_a^{e_a} \bmod I_L^+\) (ring multiplication via NTT). Run the quantum HSP algorithm: (a) Prepare uniform superposition over \(G_L\). (b) Query the oracle \(f_L\). (c) Apply the QFT on \(G_L\). (d) Obtain one element of \(H_L^\perp\). (e) Repeat \(O(\Delta r_L)\) times to recover \(H_L\) over \(\mathbb{Z}\). ) Extract the full integer relation matrix for the \(\Delta r_L\) new units. ) Obtain a generator \(g_L\) of \(I_L\), stored in tower-factored form (Section 6). end for Set \(g\leftarrow g_k\).
PHASE 3: Classical Log-Unit CVP (Part III) Compute \(L(g)=(\log|\sigma_j(g)|)_{j\in J} \in \mathbb{R}^{n/2}\) via NTT-based polynomial evaluation [25], [26]. Project \(\mathbf{t}=\Pi_{H_0}(L(g))=L(g)-\bar\ell\cdot{}\mathbf{1}\), where \(\bar\ell=\frac{2}{n}\sum_{j\in J} \log|\sigma_j(g)|\).
//Run Babai’s nearest-plane algorithm on \(\Lambda\)// Load the Gram-Schmidt basis \(B^*\) of the log-unit lattice \(\Lambda\) (from Part I). Run Algorithm [alg:babaicvp] with input \((\Lambda, B^*, \mathbf{t})\). Obtain the CVP output \(\mathbf{v}\in \Lambda\) and residual \(\boldsymbol{\rho}=\mathbf{t}-\mathbf{v}\).
PHASE 4: Short Generator Recovery (Part III) ) Solve the linear system \(\mathbf{v}=\sum_i d_i \mathbf{b}_i\) for integers \(d_i\). Reconstruct the unit of \(\varepsilon'=\prod_i \xi_{a_i}^{d_i}\in R^\times\), where \(\xi_{a_i}\) are the cyclotomic unit basis elements. ) Compute \(g_0=g\cdot{}(\varepsilon')^{-1}\). ) Compute \(\gamma=\exp(\|\boldsymbol{\rho}\|_\infty)\) and verify \(\gamma < q/2\). if \(\gamma \ge q/2\) then Retry with a different basis ordering (probability \(< 0.10\) of failure for \(d=4\)). end if \(g_0\), \(\gamma\).
We now explain every major component of Algorithm [alg:ecdpr] in detail.
The start of this phase is a module basis matrix \(B\in R^{d \times d}\). The module-to-ideal reduction from Part II performs a successive-layer decomposition of \(B\) over ring \(R\), similar to Hermite Normal Form [11] for modules over Dedekind domains. Let \(B=Q_R\cdot{}T_R\), where \(T_R\in R^{d \times d}\) is upper triangular (with diagonal entries in \(R\setminus\{0\}\)) and \(Q_R\) accounts for the change of basis. The diagonal entries \(T_{R,ii}\) generate the successive layer ideals \(I_i=(T_{R,ii}) \subset R\). The product of these ideals equals the determinant ideal \((\det B)\). \(h_k^+=1\) (Part I) guarantees every ideal in \(R\) is principal.
The quantum phase works level by level according to the cyclotomic tower \(\mathbb{Q}\subset K_3 \subset\cdots \subset K_k\). At each level \(L\), the field \(K_L\) is a quadratic extension of \(K_{L-1}\), i.e., \([K_L: K_{L-1}]=2\). This implies each new level \(L\) contributes \(\Delta r_L=2^{L-3}\) new unit generators (Lemma 1). By working level by level, it requires to deal with \(\Delta r_L\) new units at each step. As \(\Delta r_L\) grows linearly with \(L\), the quantum HSP at each level is small.
Step 1) Norm descent. The CM structure of \(K_L\) means every unit can be decomposed into a totally real part and a root of unity. Taking the norm \(\mathop{\mathrm{N}}_{K_L/K_L^+}\) collapses the ideal \(I_L \subset R_L\) to a smaller ideal \(J_L \subset R_L^+\) in a field of half the degree. Since \(h_{K_L^+}^+=1\), the smaller ideal is principal. So, finding its generator is a PIP problem in a smaller field which can be solved recursively.
Step 2) Quantum HSP. The \(\Delta r_L\) new unit generators at level \(L\) can be found by solving the Abelian Hidden Subgroup Problem (HSP) for the extension \(K_L^+/K_{L-1}^+\). Here, the HSP encodes the integer relations among a generating set of candidate units, i.e., the hidden subgroup \(H_L\) is the lattice of multiplicative relations. The quantum algorithm prepares a superposition, queries the oracle, applies QFT, and measures to obtain a random element of \(H_L^\perp\). After \(O(\Delta r_L)\) repetitions, we get enough samples to recover \(H_L\).
Steps 3)-4): Classical relation and generator recovery. The measurements in HSP give a matrix of samples from \(H_L^\perp\). Using classical LLL lattice reduction, we can find the integer relation lattice \(H_L\), which identifies the new unit generators. Combining these with the norm generator from Step 1), we get a generator \(g_k\) of the full ideal \(I\), which is stored in tower-factored form (Section 6).
With the generator \(g\) of the ideal, we then compute its log-embedding \(L(g)\in \mathbb{R}^{n/2}\). In the power basis, this requires to evaluate a degree-\(n\) polynomial with huge coefficients at each embedding \(\sigma_j\). This might have potentially exponential cost. Instead, with tower-factored form of \(g\), Proposition [prop:factored-size] shows \(\log|\sigma_j(g)|\) can be computed in \(O(n^2 \log^2 n)\) bits from the factored representation.
As the projection \(\Pi_{H_0}\) removes the mean \(\bar\ell\) from all coordinates, we subtracts a vector proportional to \(\mathbf{1}\), which corresponds to removing the overall scale of \(g\) as the CVP distance is scale-independent.
From Algorithm [alg:babaicvp], the log-unit lattice \(\Lambda\) has rank \(r=n/2-1\), embedded in the \((n/2-1)\)-dimensional space \(H_0\). Its Gram-Schmidt basis vectors \(\mathbf{b}_i^*\) have norms \(\|\mathbf{b}_i^*\|_2=\Omega(\sqrt{n})\), which are much larger than the per-component fluctuation (variance) \(\sigma_t=O(1)\) of the target \(\mathbf{t}\). This implies every projection coefficient \(\mu_i=\langle\mathbf{t}, \mathbf{b}_i^*\rangle/\|\mathbf{b}_i^*\|^2\) has magnitude \(O(1/\sqrt{n})\ll 1/2\). So. we have \(c_i=\lfloor\mu_i\rceil=0\) for any \(i\). Thus, Babai’s algorithm returns \(\mathbf{v}=\mathbf{0}\) for short generators.
For the real PIP output \(g=g_0\varepsilon\), the target is given by \(\mathbf{t}=\Pi_{H_0}(L(g_0))+L(\varepsilon)\), i.e., a shift of the balanced target by a lattice vector \(L(\varepsilon)\in \Lambda\). Babai’s back-substitution (Infinite Capture Theorem, Part III) is linear modulo rounding, i.e., adding an integer to a rounding argument before rounding is the same as adding it after. So, Babai’s algorithm returns \(L(\varepsilon)\) regardless of its size.
The CVP output \(\mathbf{v}=L(\varepsilon)\) is the log-embedding of the unit discrepancy. We recover \(\varepsilon\) by solving for the integer exponents \(d_i\) in \(\mathbf{v}=\sum_i d_i \mathbf{b}_i\), and then form the product \(\varepsilon'=\prod_i \xi_{a_i}^{d_i}\). This gives the short generator as \(g_0=g\dot{(}\varepsilon')^{-1}\).
The approximation factor is given by \(\gamma=\exp(\|\boldsymbol{\rho}\|_\infty)\), where the residual \(\boldsymbol{\rho}=\mathbf{t}-\mathbf{v}=\Pi_{H_0}(L(g_0))\). By \(L^\infty\) Bound Theorem (Part III), we get \[\begin{align} \|\boldsymbol{\rho}\|_\infty=\sigma_d\sqrt{2\ln n} +O(\sqrt{\ln\ln n}), \label{eqinfit} \end{align}\tag{8}\] which implies \(\gamma=\exp(O(\sqrt{\log n})) \ll n^\epsilon\) for every \(\epsilon>0\).
This section answers whether the resulting approximation factor \(\gamma\) is small enough to break ML-KEM.
Theorem 1. Let \(R=\mathbb{Z}[\zeta_{2^k}]\) with \(n=2^{k-1}\ge 8\) and \(k\le 12\). For a rank-\(d\) Module-LWE instance with modulus \(q\) and a randomly generated secret key, Algorithm [alg:ecdpr] achieves a Module-SVP approximation factor as \[\begin{align} \gamma=\alpha_d\cdot{}\exp(\sigma_d \sqrt{2\ln n})\cdot{}(1+o(1)), \label{Egamma-formula} \end{align}\tag{9}\] where \(\alpha_d=\sqrt{C}\) is the module-reduction factor (Part II), with \(C\le 1.36\) for MLWE-distributed inputs. The worst-case analytic bound is \(C\le 3.10\); \(\sigma_d=\sqrt{\frac{1}{4}\sum_{j=1}^d \psi'(j)}\) is the per-component standard deviation of the log-embedding of the determinant ideal’s shortest generator (Part III). The attack satisfies the following success guarantees
\(\mathrm{med}(\gamma)<q/2\) for all standardized ML-KEM parameter sets;
\(\Pr[\gamma < q/2]> 0.99\) for \(d\le 3\);
\(\Pr[\gamma < q/2]\ge 0.90\) for \(d=4\);
With \(O(\log(1/\delta))\) independent repetitions, the attack succeeds with probability \(\ge 1-\delta\).
Proof. The Gram-Schmidt decomposition of \(B\) over \(R\) in Algorithm [alg:ecdpr] introduces a discrepancy between the module’s length and the ideal’s length. This can be quantified by the balance constant \(C\) (Part II), i.e., the ratio of the squared \(L^2\) norm of the diagonal entry of \(T_R\) to its expected value under the MLWE distribution.
Note for MLWE-distributed module matrices, \(B\) has i.i.d. small-coefficient entries. From Part II, with the optimal sign selection, the balance constant satisfies \(C\le 1.36\) with a probability larger than \(0.99\) at \(n=256\). The module-reduction factor is \(\alpha_d=\sqrt{C}\le 1.17\).
After the module-to-ideal reduction, the algorithm solves the SGP for the determinant ideal \((\det B)\). From the Trigamma Theorem (Part III) we compute the per-component variance of \(\Pi_{H_0}(L(g_0))\) as \[\begin{align} \sigma_d^2=\frac{1}{n}\|\Pi_{H_0}(L(g_0))\|_2^2 \xrightarrow{p} \frac{1}{4}\sum_{j=1}^d \psi'(j) \label{Esigmad} \end{align}\tag{10}\] when \(n\to\infty\).
The variance \(\sigma_d^2\) is independent of the modulus \(q\) and the coefficient distribution as long as it is centered with finite fourth moment. This is because the Gaussian approximation to the embedding is scale-invariant. So, we obtain approximation factor \(\gamma=\exp(\|\boldsymbol{\rho}\|_\infty)\), where \(\boldsymbol{\rho}=\Pi_{H_0}(L(g_0))\) is the CVP residual. This is a vector in \(\mathbb{R}^{n/2}\) with i.i.d. (asymptotically) coordinates, each with variance \(\sigma_d^2\). By Part III, the maximum of \(n/2\) such coordinates satisfies \[\begin{align} \|\boldsymbol{\rho}\|_\infty =\sigma_d\sqrt{2\ln n}+O(\sqrt{\ln\ln n}), \label{Elinfbound} \end{align}\tag{11}\] which is consistent with the standard extreme-value result for sub-Gaussian random variables [27], [28].
Table 3 shows values for all ML-KEM parameter sets. The trigamma values are \(\psi'(1)=\pi^2/6\approx 1.6449\), \(\psi'(2)\approx 0.6449\), \(\psi'(3) \approx 0.3949\), and \(\psi'(4) \approx 0.2838\).
| Scheme | \(d\) | \(\sigma_d\) | \(\gamma_{\rm th}\) | \(\gamma_{\rm med}\) | \(\gamma_{99\%}\) | Median margin | 99% margin |
|---|---|---|---|---|---|---|---|
| ML-KEM-512 | 2 | 0.757 | 14.5 | 9.6 | 73 | \(173\times\) | \(23\times\) |
| ML-KEM-768 | 3 | 0.819 | 17.9 | 11.4 | 90 | \(146\times\) | \(19\times\) |
| ML-KEM-1024 | 4 | 0.862 | 20.6 | 12.9 | 103 | \(129\times\) | \(16\times\) |
The tail probability is from the sub-Gaussian concentration of \(\|\boldsymbol{\rho}\|_\infty\). For \(\gamma > q/2\), the exponent would need to exceed \(\ln(q/(2\alpha_d))\approx 7.26\), while its median is \(\sigma_d\sqrt{2\ln(n/2)}\approx 2.69\). The gap of \(\approx 4.6\) is more than \(5\times\) the per-component standard deviation \(\sigma_4=0.861\), and in units of the Gumbel fluctuation scale \(\sigma_G \approx 0.28\).
For \(d=4\), in actual ring model with \(n=256\), Monte Carlo simulation (\(10^5\) trials with both uniform mod-\(q\) and CBD (\(\eta=2\)) coefficient distributions) confirms the Gaussian-model prediction, we get zero failures. The largest empirical \(\gamma\) across all trials gives an empirical 99% \(\gamma_{99\%} \approx 103\), which is still below \(q/2=1664.5\). For \(d\le 3\), both the Gaussian analysis and simulation give \(\Pr[\gamma > q/2] < 10^{-3}\).
In all cases, using \(O(1)\) independent repetitions with fresh basis orderings can reduce the per-attack failure probability below \(10^{-6}\) (Section [subStail]). ◻
We use the threshold \(\gamma<q/2\) in this series which is the loosest sufficient condition for key recovery c=[9]. This guarantees the recovered vector has coordinates in \(\{-(q-1)/2, \dots, (q-1)/2\}\) and can be uniquely decoded modulo \(q\). Using a tighter bounded-distance decoding (BDD) for the CBD noise distribution with standard deviation \(\sigma_{\rm noise}=1\) might give a more restrictive threshold \(\gamma\lesssim q/(c\sigma_{\rm noise}\sqrt{dn})\) with a constant \(c\) [7], [24].
Table 1 (Part III) confirms that the ratio \(\sigma_{\boldsymbol{t}}/ \min_i\|\mathbf{b}_i^*\|\) decreases monotonically with \(n\) and is consistent with the theoretical rate \(\Theta(1/\sqrt{n/\log n})\), where \(\sigma_{\boldsymbol{t}}=\frac{\pi}{2\sqrt{6}}\approx 0.64\) is the per-component standard deviation of structured targets from Theorem 4.1 (Part III). This validates the Coarse Lattice Theorem (Part III) for all ML-KEM parameters. The empirical scaling is consistent with heuristic regulator estimates [10], and the condition holds with large margin at all tested parameters (\(\sigma_{\boldsymbol{t}}/\min_i\|\mathbf{b}_i^*\|\le 0.32\) even at \(k=4\)). A rigorous asymptotic lower bound on the Gram-Schmidt norms of the cyclotomic-unit basis remains an open problem.
For \(d=4\), the empirical median is \(\gamma_{\rm med} \approx 12.9\) with \(\gamma_{99\%} \approx 103\) and zero failures in \(10^5\) simulation trials. All values lie far below the threshold \(q/2=1664.5\). The modest spread between median and 99% is due to occasional near-zero determinant embeddings at one of the \(n/2\) complex embedding sites. This subsection quantifies the tail.
Proposition 2. For a random rank-\(d\) MLWE module over \(R\) with i.i.d. bounded coefficients, the empirical median, \(\gamma_{99\%}\), and success probabilities are given in Table 4, based on \(10^5\)-trial ring simulations at \(n=256\).
| \(d\) | \(\mathrm{med}(\gamma)\) | \(\gamma_{99\%}\) | \(\Pr[\gamma< q/2]\) | 99% margin to \(q/2=1664.5\) |
|---|---|---|---|---|
| 2 | 9.6 | 73 | >0.999 | \(23\times\) |
| 3 | 11.4 | 90 | > 0.999 | \(19\times\) |
| 4 | 12.9 | 103 | > 0.999 | \(16\times\) |
Proof. We analyze the tail in two stages: (i) the asymptotic Gaussian-model prediction, and (ii) the empirical finite-\(n\) distribution measured by ring simulation.
Gaussian-model. At each embedding \(j\in J\) (\(|J|=n/2=128\)), the matrix \(\sigma_j(B)\in \mathbb{C}^{d \times d}\) has asymptotically i.i.d. \(\mathcal{CN}(0, n\sigma_c^2)\) entries [29]. For such a random matrix, the smallest singular value \(s_{\min}\) satisfies [30]: \[\begin{align} \Pr[s_{\min} < \epsilon\tau] \approx (d\epsilon)^2 \quad\text{for small }\epsilon, \label{eqprobs} \end{align}\tag{12}\] where \(\tau^2=n\sigma_c^2\). The Gaussian-model tail probability for the \(L^\infty\) norm exceeding the threshold \(T=\ln(q/(2\alpha_d))\approx 7.3\) is dominated by the sub-Gaussian tail of the maximum of \(n/2\) coordinates, each with variance \(\sigma_d^2\). The median of \(\|\boldsymbol{\rho}\|_\infty\) is \(\sigma_d\sqrt{2\ln(n/2)}\approx 2.7\), and the gap to the threshold is \(T-2.7 \approx 4.6\), which exceeds 5 standard deviations of \(\sigma_4\). Under the Gaussian model, \(\Pr[\|\boldsymbol{\rho}\|_\infty>T]<10^{-7}\) for all \(d\le 4\).
Empirical finite-\(n\) distribution. We implement ring simulation with \(n=256\) confirms the Gaussian prediction, i.e., output zero failures across \(10^5\) trials at \(d=4\) with both uniform mod-\(q\) and CBD (\(\eta=2\)) coefficient distributions. The empirical distributions are \[\begin{align} d=2: &\quad \gamma_{\rm med}=9.6, \quad \gamma_{99\%}=73, \quad \gamma_{\max}\le 200; \\ d=3: &\quad \gamma_{\rm med}=11.4, \quad \gamma_{99\%}=90, \quad \gamma_{\max}\le 200; \\ d=4: &\quad \gamma_{\rm med}=12.9, \quad \gamma_{99\%}=103, \quad \gamma_{\max}\le 200. \end{align}\] The \(\gamma_{99\%}\) is approximately \(5\times\) the median in all three cases, shows the heavy tail induced by occasional near-zero embeddings of \(\det(\sigma_j(B))\). However, even in the worst observed cases, \(\gamma\) remains below \(q/2=1664.5\).
For \(d=4\), with one independent repetition (using a different basis ordering), the probability that both attempts produce \(\gamma > q/2\) is empirically below \(10^{-6}\). ◻
When \(\gamma > q/2\), we can use three strategies as follows: a different ordering of the module basis columns changes the Gram-Schmidt decomposition and may yield a more balanced determinant; applying BKZ [17] to \(B\) before the CDPR pipeline; attacking each secret component independently reduces the effective module rank to \(d=1\).
The quantum phase of Algorithm [alg:ecdpr] relies on a polynomial-time quantum algorithm for the Principal Ideal Problem (PIP). While all prior polynomial-time descriptions of the Biasse-Song algorithm [31] hide an exponential coefficient blowup, this section presents a tower-based PIP algorithm which gives the first polynomial-time construction.
A unit \(\varepsilon\in R_k^\times\) in the standard power basis is represented by \(\varepsilon=\sum_{i=0}^{n-1} a_i \zeta^i\) with \(a_i\in \mathbb{Z}\). The fundamental units are cyclotomic units \(\xi_a=\sin(a\pi/m)/\sin(\pi/m)\) for odd \(a\) [10], [21]. A general unit is a product as \[\begin{align} \varepsilon=\prod_{a\text{ odd}} \xi_a^{e_a}, \end{align}\] where the exponents \(e_a\in \mathbb{Z}\) can be \(O(n)\) in size from the CVP/Babai step in the CDPR attack [9]. Expanding this product in the power basis, each multiplication can double the coefficient size [32]. So, one may have coefficients with \(2^{O(n)}\) bits.
Meanwhile, the Biasse-Song algorithm requires generalized Riemann hypothesis (GRH) for number fields of degree up to \(n=256\) [31].
The key of the present method to resolving both coefficient explosion and GRH is to process one quadratic extension at a time. The cyclotomic tower is the chain of nested subfields as \[\begin{align} \mathbb{Q}\subset K_3=\mathbb{Q}(\zeta_8) \subset K_4=\mathbb{Q}(\zeta_{16}) \subset\cdots \subset K_k=\mathbb{Q}(\zeta_{2^k}), \label{Etower} \end{align}\tag{13}\] where \([K_L: K_{L-1}]=2\) for every \(L \ge 4\).
Lemma 1. For all \(L \ge 3\), the following results hold
\([K_L: K_{L-1}]=2\);
\(\mathop{\mathrm{rk}}(R_L^\times)=2^{L-2}-1\);
\(\Delta r_L:= \mathop{\mathrm{rk}}(R_L^\times)-\mathop{\mathrm{rk}}(R_{L-1}^\times)=2^{L-3}\) for \(L \ge 4\), and \(\Delta r_3=1\);
\(\ker(\mathop{\mathrm{N}}_{K_L/K_L^+:} R_L^\times \to (R_L^+)^\times)=\mu_{2^L}\) (finite torsion of order \(2^L\));
All \(\Delta r_L\) new free unit generators at level \(L\) lie in the totally real subtower \(K_L^+/K_{L-1}^+\).
Proof. Part (i) is from \(\zeta_{2^L}^2=\zeta_{2^{L-1}}\), so \(\zeta_{2^L}\) satisfies the quadratic \(x^2-\zeta_{2^{L-1}}\in K_{L-1}[x]\), which is irreducible as \(\zeta_{2^L} \notin K_{L-1}\). Part (ii) is from the Dirichlet’s Unit Theorem [11], [12] with \(r_1=0\) and \(r_2=2^{L-2}\). Result (iii) is easy to followed from (ii). Part (iv) is from the kronecker’s Theorem [10], [11], i.e., any algebraic integer with all embeddings on the unit circle is a root of unity. (v) is from \(\mathop{\mathrm{rk}}(R_L^\times)=\mathop{\mathrm{rk}}((R_L^+)^\times)\). So, the CM kernel has rank 0 and all free units come from the real subfield. ◻
Definition 5. A unit \(\varepsilon\in R_k^\times\) is in tower-factored form if it is stored as a product of relative units across the tower as \[\begin{align} \varepsilon=\varepsilon_3\cdot{}\varepsilon_4\cdots \varepsilon_k, \quad \varepsilon_L\in R_L^\times/R_{L-1}^\times, \end{align}\] where each \(\varepsilon_L\) is stored as a linear polynomial \(\varepsilon_L=a_L+b_L \zeta_{2^L}\) with \(a_L, b_L\in R_{L-1}\), themselves in tower-factored form for the \((L-1)\)-level tower.
Proposition 3. A unit in tower-factored form has total storage size \(O(n^2 \log n)\) bits, and evaluation cost \(O(n^2 \log^2 n)\) bit operations for any single log-embedding \(\log|\sigma_j(\varepsilon)|\).
Proof. At level \(L\), the factor \(\varepsilon_L\) has \(n_L=2^{L-1}\) leaf integers, each requires \(O(L\cdot{}2^L)\) bits. Storing at level \(L\) then costs \(O(n_L\cdot{}L\cdot{}2^L)=O(L\cdot{}2^{2L-1})\). So, we get for all \(L\) levels \[\begin{align} \sum_{L=3}^k O(L\cdot{}2^{2L})=O(k\cdot{}2^{2k})=O(n^2\log n). \label{eqcostsum} \end{align}\tag{14}\] Here, our evaluation uses the multiplicative structure of \(\sigma_j(\varepsilon)=\prod_{L=3}^k \sigma_j(\varepsilon_L)\), where each factor costs \(O(n_L\cdot{}L^2\cdot{}2^L)=O(L^2\cdot{}2^{2L})\) bit operations from fast integer multiplication [33]. The total cost is \(\sum_{L=3}^k O(L^2\cdot{}2^{2L})=O(k^2\cdot{}2^{2k})=O(n^2 \log^2 n)\). ◻
The tower-factored form stores a unit as a product of relative factors \(\varepsilon=\varepsilon_3\cdots \varepsilon_k\). We obtain from \(\varepsilon\cdot{}\varepsilon'\) per-level products \(\varepsilon_L\cdot{}\varepsilon_L'\), which are elements of \(R_L^\times\) but need not themselves be relative units at level \(L\). In this case, we can use a polynomial-time normalization after each multiplication to restore the representation invariant \(\varepsilon_L\in R_L^\times/R_{L-1}^\times\).
We now state the main complexity theorem and complete quantum algorithm.
Theorem 4. Given a principal ideal \(I\subset R_k\) with \(h_k^+=1\) and \(k\le 12\), there exists a quantum algorithm (Algorithm [alg:tower-pip]) generating a generator \(g\) with \((g)=I\), using \(O(n^3 \log^2 n)\) quantum gates, \(O(n^2 \log n)\) qubits, and \(O(n^{5+\epsilon})\) classical bit operations.
Polynomial Tower PIPalg:tower-pip
INPUTS: \(I\subset R_k\): a principal ideal, given by a \(\mathbb{Z}\)-basis \(k\le 12\): the tower level (\(h_k^+=1\), Part I)
OUTPUT: \(g\in R_k\): a generator of \(I\), i.e., \((g)=I\), stored in tower-factored form (Definition 5)
BASE CASE (\(L=3\)): \(K_3=\mathbb{Q}(\zeta_8)\), degree \(n_3=4\), unit rank \(r_3=1\) Compute the unit \(\xi_3=\zeta_8+\zeta_8^{-1}=\sqrt{2}\). Compute \(I_3=I \cap R_3\). Find \(e\) such that \(I_3=(\xi_3^e)\) by rounding: \(e=\lfloor \log_{\xi_3}\mathop{\mathrm{N}}(I_3) / 2 \rceil\). Set \(g_3\leftarrow\xi_3^e\), stored as the integer pair \((e, 0)\) in tower-factored form.
INDUCTIVE STEP: for \(L=4, 5, \dots, k\) (Assume PIP for \(K_{L-1}\) has been solved; solve for \(K_L\).)
Step 1: Compute the norm ideal: \(J_L=\mathop{\mathrm{N}}_{K_L/K_L^+}(I_L)=I_L\cdot{}\overline{I_L}\subset R_L^+\). Solve PIP for \(J_L\) in \(K_L^+\) recursively using real subtower \(K_3^+ \subset\cdots \subset K_L^+\). Obtain a generator \(g_L^+\in R_L^+\) of \(J_L\), stored in tower-factored form.
Step 2: Set the precision: \(b_L\leftarrow \lceil 10\cdot{}L\cdot{}2^L \rceil\) bits. Enumerate \(\Delta r_L=2^{L-3}\) new relative units at level \(L\): \[\begin{align} \mathcal{U}_L=\{\xi_a: a \text{ odd}, 2^{L-2} < a < 2^{L-1}\} \end{align}\] Set HSP group: \(G_L=(\mathbb{Z}/2^{b_L}\mathbb{Z})^{\Delta r_L}\), encoding integer exponent vectors for new units. Quantum subroutine: Initialize \(\Delta r_L\) quantum registers, each of \(b_L\) qubits, in uniform superposition: \[\begin{align} |\psi_0\rangle=\frac{1}{\sqrt{2^{b_L \Delta r_L}}} \sum_{(e_1,\dots,e_{\Delta r_L})\in G_L} |e_1, \dots, e_{\Delta r_L}\rangle |0\rangle. \end{align}\] Query quantum oracle \(f_L: G_L \to R_L^+/I_L^+\) defined by \[\begin{align} f_L(e_1, \dots, e_{\Delta r_L}) =\prod_{a\in \mathcal{U}_L}\xi_a^{e_a}\bmod I_L^+ \end{align}\] which is implemented using NTT-based ring multiplication [25]. Apply the QFT on each register of \(G_L\). Measure the first register; obtain one sample \(s\in H_L^\perp\), where \(H_L=\ker(f_L)\). Repeat lines 11-16 \(N_{\rm rep}=O(\Delta r_L)\) times to collect samples \(s_1, \dots, s_{N_{\rm rep}}\in H_L^\perp\).
Step 3: Reshape the sample matrix \(S_L\in \mathbb{Z}^{N_{\rm rep} \times \Delta r_L}\) with rows \(s_1, \dots, s_{N_{\rm rep}}\). Run LLL lattice reduction on the kernel lattice of \(S_L\) to recover a full basis for \(H_L\). Extract \(\Delta r_L\) integer relation vectors \(\mathbf{h}_1, \dots, \mathbf{h}_{\Delta r_L}\) from the LLL basis. Check \(\prod_{a\in \mathcal{U}_L}\xi_a^{(h_j)_a}\in R_{L-1}^\times\) for each \(j\), products are units in previous level’s ring.
Step 4: Solve discrete logarithm problem as:
find \(\mathbf{d}\in\mathbb{Z}^{\Delta r_L}\) such that \(\mathop{\mathrm{N}}_{K_L/K_L^+}(g_L^{\rm candidate})=g_L^+\cdot{}u_L^+\) for some \(u_L^+\in (R_{L-1}^+)^\times\). Construct: \(g_L=g_{L-1}\cdot\varepsilon_L\), \(\varepsilon_L\in R_L^\times/R_{L-1}^\times\) is a relative unit correction from Step 3. Verify \((g_L)=I_L\) by checking ideal equality in \(R_L\).
\(g\leftarrow g_k\), stored in tower-factored form.
We show Algorithm [alg:tower-pip] by induction on the tower level \(L\). For \(L=3\), it is trivial because the unit group is one-dimensional.
\(L=3\). The unit group of \(R_3=\mathbb{Z}[\zeta_8]\) has rank 1, generated by \(\sqrt{2}\) up to torsion \(\mu_8\). The ideal \(I_3=(\xi_3^e)\) for a unique \(e\) determined by \(\mathop{\mathrm{N}}(I_3)=2^{|e|}\). The Babai’s rounding can identify \(e\) exactly. So, the base case is correct.
Inductive step. Assume the algorithm can correctly solve PIP for all fields up to level \(L-1\). We verify each step for the level \(L\):
Step 1: The ideal \(J_L=\mathop{\mathrm{N}}_{K_L/K_L^+}(I_L)\) is a principal ideal in \(R_L^+\) as \(h_{K_L^+}^+=1\) (Part I). The recursion on the totally real subtower finds \(g_L^+\) correctly by the inductive hypothesis applied to \(K_L^+\).
Step 2: The hidden subgroup \(H_L\) encodes integer relations among the generating set \(\mathcal{U}_L\). The abelian HSP algorithm [1], [34] can find \(H_L^\perp\), and recover \(H_L\) with probability \(1-2^{-\Omega(\Delta r_L)}\) from \(O(\Delta r_L)\) samples.
Step 3: The precision \(b_L=O(L\cdot{}2^L)\) exceeds the logarithm of the determinant of the relation sublattice \(H_L \subset G_L\), such that LLL algorithm can find the full relation basis [16].
Step 4: The discrete logarithm over \(\mathbb{Z}\) can be solved in polynomial time. The output \(g_L\) satisfies \((g_L)=I_L\) by construction.
By induction, the algorithm is correct for all \(L\le k\).
Now, we estimate the complexity. At level \(L\), the dominant costs are given by \[\begin{align} \text{Quantum gates} &: O(\Delta r_L)\cdot{}O(n_L \log n_L\cdot{}\Delta r_L) =O(2^{2(L-3)}\cdot{}2^{L-1}\cdot{}L) =O(L\cdot{}2^{3L-7}), \\ \text{Qubits} &: \Delta r_L\cdot{}b_L=O(2^{L-3}\cdot{}L\cdot{}2^L)=O(L\cdot{}2^{2L-3}), \\ \text{Bit operations} &: O(\Delta r_L^5\cdot{}b_L^2)=O(2^{5(L-3)}\cdot{}L^2\cdot{}2^{2L}) =O(L^2\cdot{}2^{7L-15}). \end{align}\] As it is dominated by the top level \(L=k\), we obtain the total costs as \[\begin{align} Q_{\rm total} &= \sum_{L=3}^k O(L\cdot{}2^{3L})= O(n^3 \log n), \\ N_{\rm qubits} &= O(k\cdot{}2^{2k})=O(n^2 \log n), \\ C_{\rm bit} &= \sum_{L=3}^k O(L^2\cdot{}2^{7L}) =O(n^7 \log^2 n) \end{align}\] with \(n=2^{k-1}\) and \(k=O(\log n)\). The \(O(n^3 \log^2 n)\) quantum gates is followed by including the \(O(\log n)\) factor from QFT precision [26], [35]. The classical cost can be further reduced to \(O(n^{5+\epsilon})\) using the \(L^2\) algorithm [36].
This subsection present logical and physical resource for the ML-KEM-1024 parameter set (\(k=9\), \(n=256\)), under surface code assumptions [37], [38] (code distance \(d \approx 30\), targeting a logical error rate of \(10^{-15}\)). The dominant cost is from the quantum HSP at the top tower level \(L=9\), i.e., \(\Delta r_9=64\) new relative units and 64 independent HSP runs, each using NTT-based ring multiplication [25] as the oracle. Table 5 summarizes all costs.
| Resource | Estimated Value |
|---|---|
| New units at top level (\(\Delta r_9\)) | 64 |
| HSP repetitions at top level | 64 |
| Oracle gates per HSP call (NTT, \(n=256\)) | \(\approx 2048\) |
| Per-HSP QFT cost (top level) | \(\approx 2 \times 10^4\) |
| Total logical gates (top level) | \(\approx 9 \times 10^7\) |
| Total logical gates (all levels) | \(\approx 2^{27}\) |
| Logical qubits | \(\approx 1400\) |
| Physical qubits (surface code, \(d=30\), \(10^{-15}\) error) | \(\approx 1.4 \times 10^6\) |
| Physical gate operations | \(\approx 2^{37}\) |
In this section, we show the cyclotomic tower, the Trigamma Theorem, Babai’s algorithm on the log-unit lattice can be applied to any lattice-based scheme based on a 2-power cyclotomic ring \(\mathbb{Z}[\zeta_{2^k}]\). Specially, we analyze Falcon [39], Hawk [40], and NTRU over 2-power cyclotomics [41], [42].
We state three algebraic conditions (A1)-(A3), together with a sufficiency theorem asserting that they are all that is needed to run our attack.
Trivial plus-class number. The maximal totally real subfield \(K^+=\mathbb{Q}(\zeta_{2^k})^+\) satisfies \(h_{K^+}=1\), i.e., every ideal of \(\mathcal{O}_{K^+}\) is principal. This holds for every \(k\le 12\) (Part I).
Binary cyclotomic tower. The field \(K=\mathbb{Q}(\zeta_{2^k})\) is at the top of the tower \(\mathbb{Q}\subset K_3 \subset K_4 \subset\cdots \subset K_k=K\), where each step is a quadratic extension. By Lemma 1, this holds for any \(k \ge 3\).
Trigamma variance formula. For the rank-\(d\) module determinant ideal generated by a random module matrix \(B\in R^{d \times d}\) with i.i.d. centered coefficients of finite fourth moment, the per-component variance of the log-embedding of the shortest generator satisfies \[\begin{align} \sigma_d^2 \xrightarrow{p} \frac{1}{4}\sum_{j=1}^d \psi'(j) \quad\text{as } n \to\infty, \label{Etrigammapre} \end{align}\tag{15}\] where \(\psi'\) is the trigamma function (Part III).
Theorem 5. Let \(\Pi\) be a lattice-based cryptographic scheme whose key-recovery problem reduces to Module-SVP or to PIP (e.g. via Module-LIP [43], [44]) over the ring \(R=\mathbb{Z}[\zeta_{2^k}]\) with \(k\le 12\) and effective module rank \(d\). Suppose conditions (A1), (A2), and (A3) hold. Then Algorithm [alg:ecdpr] applies to \(\Pi\) and achieves the approximation factor as \[\begin{align} \gamma=\alpha_d\cdot{}\exp(\sigma_d \sqrt{2\ln n})\cdot{}(1+o(1)), \label{Egammagral} \end{align}\tag{16}\] where \(\alpha_d=\sqrt{C}\) with \(C\le 1.36\) for module-distributed inputs (Part II), and \(\sigma_d=\sqrt{\frac{1}{4}\sum_{j=1}^d\psi'(j)}\) from (A3). Attack success probability and tail bounds are shown as in Theorem 1.
Proof. Theorem 1 shows Eq.@eq:Egammagral under the hypotheses (A1)-(A3), and its proof depends only on the ring structure (used in the PIP step), the tower structure (used in Algorithm [alg:tower-pip]), and the Trigamma Theorem (used in the variance formula for the CVP residual). All these can be ensured by (A1)-(A3), independently of the specific scheme \(\Pi\). ◻
Falcon [39], slated for standardization as FIPS 206 (FN-DSA) [45], is a hash-and-sign signature scheme based on the GPV framework [46]. It uses the ring \(R=\mathbb{Z}[\zeta_{2n}]=\mathbb{Z}[x]/(x^n+1)\) with \(n\in \{512, 1024\}\) and prime modulus \(q=12289\). The public key is a rational function \(h=g\cdot{}f^{-1} \bmod q\), where \((f, g)\in R^2\) is a short pair of ring elements satisfying \(\|f\|_2^2+\|g\|_2^2 \approx q\). The corresponding NTRU lattice is defined by \[\begin{align} \Lambda_h=\{(u,v)\in R^2: u+vh \equiv 0 \pmod{q}\}, \label{Efalconlatti} \end{align}\tag{17}\] which has a short basis \((f, g; F, G)\) satisfying the NTRU equation \(f\cdot{}G-g\cdot{}F=q\) in \(R\).
The security of Falcon’s key-recovery has been reduced to the Short Basis Problem (SBP) for \(\Lambda_h\) [46]: given only \(h\), find a short basis of \(\Lambda_h\). The SBP can be further reduced to the SGP for the determinant ideal of \(\Lambda_h\).
Lemma 2. Let \(\Lambda_h\) be Falcon NTRU lattice and \(I=(\det \Lambda_h)=(q) \subset R\) be its determinant ideal. Any short basis \((f, g; F,G)\) of \(\Lambda_h\) satisfies \(f\cdot{}G-g\cdot{}F=q\), so \((f,g)\) is a short generator of the principal ideal \((q)\) in \(R\). Conversely, any short generator of ideal \((q)\) yields a short basis using the extended Euclidean algorithm over \(R\), at polynomial classical cost.
Proof. Consider \(2n \times 2n\) integer basis matrix of \(\Lambda_h\) formed by the rows of \((f, g)\) and \((F, G)\) in coefficient-vector form. Its determinant is \(|\det \Lambda_h|=q^n\), as an ideal norm. Since every ideal of \(R\) is principal under condition (A1), the ideal \((q^n)\) has a generator \(g_0=f\cdot{}G-g\cdot{}F\). Solving the NTRU equation yields \(g_0=q\). From a short pair \((f,g)\) we can identify both a short generator of ideal \((q)\subset R\) and the full short basis. Using the extended Euclidean algorithm over \(R\), it costs \(O(n^2)\) ring operations [16]. ◻
Proposition 6. Both Falcon parameter sets satisfy conditions (A1), (A2), and (A3).
Proof. (A1) Falcon-512 uses \(\zeta_{1024}\), corresponding to \(k=10\) while Falcon-1024 uses \(\zeta_{2048}\), corresponding to \(k=11\). By Part I, we have \(h_{10}^+=1\) and \(h_{11}^+=1\) unconditionally. Hence, every ideal in the totally real subring \(\mathcal{O}_{K^+}\) is principal, which implies the norm-descent step of Algorithm [alg:tower-pip] produces a principal ideal.
(A2) The ring \(R=\mathbb{Z}[\zeta_{2n}]\) for \(n\in \{512, 1024\}\) is the 2-power cyclotomic ring of Lemma 1, with \(m=2n=2^{k}\) and \(k\in \{10, 11\}\). Note the cyclotomic tower \(\mathbb{Q}\subset \mathbb{Q}(\zeta_8) \subset\cdots \subset \mathbb{Q}(\zeta_{2n})\) has \(k-2\) levels, each a quadratic extension. We can apply Algorithm [alg:tower-pip].
(A3) The Falcon NTRU lattice \(\Lambda_h\) is a rank-\(2\) module over \(R\). Its determinant ideal is \((q) \subset R\), and \(q\) is a rational integer whose log-embedding projects to \(\mathbf{0}\in H_0\) as all embeddings of a rational integer have equal modulus. So, we have the determinant ideal \(\sigma_{(q)}=0\). In this case, we extend CDPR to target the first Gram-Schmidt ideal \((f) \subset R\), where \(f\) is a random ring element with i.i.d. centered coefficients of variance \(\sigma_f^2\) from a discrete Gaussian distribution [39]. Since \(f\) is a single random ring element, the Trigamma rank is \(d=1\), which then gives \[\begin{align} \sigma_1^2=\frac{1}{4}\psi'(1)=\frac{\pi^2}{24}\approx 0.4112, \sigma_1 \approx 0.641. \label{Efalconsigma} \end{align}\tag{18}\] As a conservative upper bound, we may use the generic rank-2 formula \(\sigma_2=\sqrt{[\psi'(1)+\psi'(2)]/4}\approx 0.757\), bounding the worst-case Gram-Schmidt layer of any rank-2 module. Both values are used in Theorem 7, where \(\sigma_1\) gives the tighter bound for the real attack, while \(\sigma_2\) provides a safe upper bound. ◻
Theorem 7. For Falcon-\(n\) with \(n\in \{512, 1024\}\) and \(q=12289\), the Algorithm [alg:ecdpr] applied to the NTRU lattice \(\Lambda_h\) achieves the approximation factor as \[\begin{align} \gamma_n=\alpha_2\cdot{}\exp\bigl(\sigma_2 \sqrt{2\ln n}\bigr) \cdot{}(1+o(1)), \label{EFalcogam} \end{align}\tag{19}\] where \(\sigma_2=0.757\) and \(\alpha_2\le 1.17\). Simulation gives explicit values as
| Scheme | \(\sqrt{2\ln n}\) | \(\gamma_{\rm th}\) | \(\gamma_{99\%}\) | Margin |
|---|---|---|---|---|
| Falcon-512 | 3.53 | \(16.9\) | \(85\) | \(\le 72\) |
| Falcon-1024 | 3.72 | \(19.6\) | \(98\) | \(\le 63\) |
All values satisfy \(\gamma_{99\%} \ll q/2=6145\).
Proof. Proposition 6 verifies conditions (A1)-(A3) for both Falcon parameter sets. Theorem 5 applies with \(d=2\) and \(\sigma=\sigma_1\) (first GS layer, corresponding to the ideal \((f)\)) or \(\sigma=\sigma_2\) (conservative bound over both GS layers). ◻
The the extended attack on Falcon targets the principal ideal \((f)\subset R\) generated by the secret key component \(f\), not the determinant ideal \((q)\) which has trivial log-embedding.
Proposition 8. Given the short generator \(g_0\) recovered by Algorithm [alg:ecdpr], the complete Falcon secret key \((f, g; F, G)\) can be reconstructed in polynomial classical time.
Proof. By Lemma 2, a short generator of \((q)\) in \(R\) is the element \(f\cdot{}G-g\cdot{}F=q\). From the output \(g_0 \approx f\) (recovered as the shortest generator of the principal ideal \((f)\) in \(R\)), the remained key components are obtained as follows. First, we compute \(g \equiv f\cdot{}h \pmod{q}\) directly from the public key \(h\). Second, we solve NTRU equation \(f\cdot{}G-g\cdot{}F=q\) by the extended Euclidean algorithm over \(R\), costing \(O(n^2 \log n)\) bit operations [16] and returning \((F, G)\) satisfying \(\|F\|_\infty, \|G\|_\infty=O(\sqrt{q \log n})\). The recovered key can pass the validity check with a probability \(1-\exp(-\Omega(n))\) whenever \(\gamma < q/2\). ◻
Hawk [40] is a lattice signature scheme over the 2-power cyclotomic ring \(R=\mathbb{Z}[x]/(x^n+1)\) with \(n\in \{256, 512, 1024\}\). The secret key is a basis \(B\in R^{2\times 2}\) for \(\mathbb{Z}^{2n}\) under a hidden quadratic form. Hawk is not a Module-LWE scheme. In particular, there is no modulus \(q\) in the sense used in ML-KEM or ML-DSA. It is a Module-LIP (Lattice Isomorphism Problem) scheme. Signatures are short vectors verified against a public Gram matrix \(Q=B^*\cdot{}B\), and the verification bound is the Q-norm \[\begin{align} \langle\mathbf{s}, Q\mathbf{s}\rangle\le \sigma_{\rm ver}^2\cdot{}8n, \label{eqQnorm} \end{align}\tag{20}\] i.e., the signature norm is bounded by \(\beta_{\rm Hawk}=\sigma_{\rm ver}\sqrt{8n}\), where \(\sigma_{\rm ver}\) takes 1.042, 1.425, 1.571 for Hawk-256/512/1024 respectively. Note only Hawk-512 (NIST Level 1) and Hawk-1024 (NIST Level 5) are official parameter sets.
Lemma 3. [43] Given the Hawk public key \(h=g\cdot{}f^{-1}\in R_2\) (where \(R_2=R/2R\)), recovering the secret key \((f, g; F, G)\) is polynomial-time equivalent to solving the PIP for the principal ideal \((f) \subset R\) in the ring \(R=\mathbb{Z}[\zeta_{2n}]\).
Proposition 9. For \(n\in \{256, 512, 1024\}\), conditions (A1)-(A3) for the CDPR attack hold: (A1) \(h_k^+=1\) for the corresponding conductors \(k\in \{9, 10, 11\}\) by Part I; (A2) The 2-power cyclotomic tower applies directly, \(n=2^{k-1}\); (A3) The PIP target \((f)\) has \(f\) sampled from a centered binomial distribution. As Hawk’s NTRU-equation \(f\cdot{}G-g\cdot{}F=1\) effectively gives a rank-2 short-vector problem, so we use the conservative \(d=2\) bound \(\sigma_2=0.7566\).
Theorem 10. The present extended CDPR method applied to the PIP target \((f)\) (Lemma 3) achieves the margin \(\beta_{\rm Hawk}/\gamma_{99\%}^{\rm form}\) with \(\gamma_{99\%}^{\rm form}=5\gamma_{\rm th}\), and the empirical margin \(\beta_{\rm Hawk}/\gamma_{99\%}^{\rm emp}\) from a \(10^5\)-trial i.i.d.-Gaussian and max simulation as
| Scheme | \(n\) | \(\sigma_v\) | \(\beta_{\rm Hawk}\) | \(\gamma_{\rm th}\) | \(\gamma_{99\%}^{\rm form}\) | \(\gamma_{99\%}^{\rm emp}\) | Margin formula | Margin emp |
|---|---|---|---|---|---|---|---|---|
| Hawk-256\(^\dagger\) | 256 | 1.042 | 47 | 14.5 | 73 | 23 | \(0.65\times\) | \(2.02\times\) |
| Hawk-512 | 512 | 1.425 | 91 | 16.9 | 85 | 26 | \(1.08\times\) | \(3.47\times\) |
| Hawk-1024 | 1024 | 1.571 | 142 | 19.6 | 98 | 29 | \(1.45\times\) | \(4.84\times\) |
\(^\dagger\) HAWK-256 is conditionally broken: the median attack succeeds (\(\gamma_{\rm th}=14.5<\beta=47\)), and the i.i.d Gaussian simulation succeeds in \(99.99\%\) of \(10^5\) trials. While the formal \(\kappa=5\) upper bound \(\gamma_{99\%}^{\rm form}=73\) exceeds the threshold \(\beta=47\), classifying it as not broken under the most conservative measure.
Hawk’s margins are much tighter than those of ML-KEM or Falcon as the signature-norm bound \(\beta=\sigma_{\rm ver}\sqrt{8n}\) is far smaller than a typical modulus \(q/2\).
Proposition 11. Given the short generator \(f_0\) recovered by Algorithm [alg:ecdpr], the full Hawk secret key \((f, g; F, G)\) is reconstructed in \(O(n^2\log n)\) classical bit operations.
Proof. By Lemma 3, \(f_0\) is the shortest generator of the ideal \((f) \subset R\). Compute \(g_0=f_0\cdot{}h \bmod 2\). Solve \(f_0\cdot{}G_0-g_0\cdot{}F_0=1\) by using the extended Euclidean algorithm over \(R\) [43], [44]. The solution exists as \(\gcd(f_0, g_0)=1\) in \(R\). This is from the NTRU equation \(f\cdot{}G-g\cdot{}F=1\) and \(f_0\approx f\). ◻
NTRU [47] over the 2-power cyclotomic ring \(R=\mathbb{Z}[x]/(x^n+1)\) uses the same NTRU lattice 17 as Falcon: (i) it uses different parameter ranges for \((f, g)\), and (ii) the NIST-standardized variants (NTRU-HPS and NTRU-HRSS) use \(R'=\mathbb{Z}[x]/\Phi_p(x)\) for prime conductor \(p\), not a 2-power cyclotomic ring. This subsection analyses the 2-power cyclotomic NTRU variants [41].
The main difference from Falcon is the coefficient distribution. In NTRU-HPS with parameter \(q\), the secret \(f\) is drawn from the set of ternary polynomials \(\{-1, 0, 1\}^n\) subject to a weight constraint, while in NTRU-HRSS, \(f\) is a uniformly random product of two small ternary elements.
Proposition 12. For NTRU over \(R=\mathbb{Z}[x]/(x^n+1)\) with \(n=2^{k-1}\), \(k\le 11\), and \(q\) a prime, all conditions (A1), (A2), and (A3) hold.
Proof. (A1) For \(k\le 11\), we have \(h_k^+=1\) from Part I.
(A2) As the ring \(R=\mathbb{Z}[\zeta_{2n}]\) is 2-power cyclotomic, we can apply the tower.
(A3) We verify this condition for each NTRU variant as
NTRU-HPS: The element \(f\) has i.i.d. entries in \(\{-1, 0, 1\}\) with \(\Pr[f_i=1]=\Pr[f_i=-1]=d/(2n)\) and \(\Pr[f_i=0]=1-d/n\) for a weight parameter \(d\). The mean is \(0\), the variance is \(\sigma_f^2=d/n\), and the fourth moment is finite. We can apply condition (A3) with \(d_{\rm rank}=2\) (NTRU is a rank-2 module), which gives \(\sigma_2 \approx 0.757\) independent of \(d\) and \(q\).
NTRU-HRSS: The element \(f=f_1\cdot{}f_2\) for small \(f_1, f_2\in R\) are drawn uniformly from ternary polynomials. By the CLT for products of independent random elements [28], [29], we know the coefficients of \(f\) satisfy the condition (A3) with \(\sigma_f^2=\sigma_{f_1}^2 \sigma_{f_2}^2 n\) [28]. So, this condition holds with the same \(\sigma_2\approx 0.757\).
◻
Theorem 13. For the four NTRU-HPS/NTRU-HRSS parameter sets, the extended CDPR attack achieves \[\begin{align} \gamma=\alpha_2\cdot{}\exp(\sigma_2\sqrt{2\ln n})\cdot{}(1+o(1)), \end{align}\] with \(\sigma_2 \approx 0.757\) and \(\alpha_2\le 1.17\). The numerical values are given by
| Scheme | \(p\) | \(n=p{-}1\) | \(q\) | \(\gamma_{\rm th}\) | \(\gamma_{99\%}\) | Margin | |
|---|---|---|---|---|---|---|---|
| NTRU-HPS-2048-509 | 509 | 508 | 2048 | 16.9 | 85 | \(12.1\times\) | |
| NTRU-HPS-2048-677 | 677 | 676 | 2048 | 18.0 | 90 | \(11.4\times\) | |
| NTRU-HPS-4096-821 | 821 | 820 | 4096 | 18.7 | 94 | \(21.9\times\) | |
| NTRU-HRSS-701 | 701 | 700 | 8192 | 18.1 | 91 | \(45.2\times\) |
The class-number condition \(h_p^+=1\) for each NTRU prime is verified unconditionally in Part V.
Proposition 12 verifies conditions (A1)-(A3). From Theorem 5 we get the formula.
The NTRU attack of Kirchner and Fouque [48] exploits a different structural property and applies when \(q\) is exponentially large in \(n\). Our attack targets the short-generator structure of the NTRU ideal and applies for all \(q\), including the standard parameter regime where their attack is ineffective. The overstretched attack achieves a better approximation factor for large \(q\), while our attack gives \(\gamma=O(\exp(\sqrt{\log n}))\) independent of \(q\).
Table 6 shows approximation factors and security margins for all schemes, together with the ML-KEM baseline from Section 4.
| Scheme | Family | \(d\) | \(n\) | \(q\) | \(\gamma_{\rm th}\) | \(\gamma_{99\%}\) | Threshold | Margin |
|---|---|---|---|---|---|---|---|---|
| ML-KEM-512 | Module-LWE | 2 | 256 | 3329 | 14.5 | 73 | 1664.5 | \(23\times\) |
| ML-KEM-768 | Module-LWE | 3 | 256 | 3329 | 17.9 | 90 | 1664.5 | \(19\times\) |
| ML-KEM-1024 | Module-LWE | 4 | 256 | 3329 | 20.6 | 103 | 1664.5 | \(16\times\) |
| Falcon-512 | NTRU-GPV | 2 | 512 | 12289 | 16.9 | 85 | 6145 | \(72\times\) |
| Falcon-1024 | NTRU-GPV | 2 | 1024 | 12289 | 19.6 | 98 | 6145 | \(63\times\) |
| Hawk-256\(^\dagger\) | Module-LIP | 2 | 256 | – | 14.5 | 73 | \(\beta=47\) | \(0.65\times\) |
| Hawk-512 | Module-LIP | 2 | 512 | – | 16.9 | 85 | \(\beta=91\) | \(1.08\times\) |
| Hawk-1024 | Module-LIP | 2 | 1024 | – | 19.6 | 98 | \(\beta=142\) | \(1.45\times\) |
| NTRU-HPS-2048-509 | NTRU | 2 | 508 | 2048 | 16.9 | 85 | 1024 | \(12\times\) |
| NTRU-HPS-2048-677 | NTRU | 2 | 676 | 2048 | 18.0 | 90 | 1024 | \(11\times\) |
| NTRU-HPS-4096-821 | NTRU | 2 | 820 | 4096 | 18.7 | 94 | 2048 | \(22\times\) |
| NTRU-HRSS-701 | NTRU | 2 | 700 | 8192 | 18.1 | 91 | 4096 | \(45\times\) |
\(^\dagger\) Empirical margin \(2.02\times > 1\) under \(\kappa_{\rm emp} \approx 1.6\).
The best classical attacks on lattice problems rely on the BKZ algorithm [17], [18] and its variants [49], [50], often combined with sieving [19], [51], [52]. The fastest classical sieving solves SVP in dimension \(n\) in time and space \(2^{0.2075n+o(n)}\) [19]. For Module-LWE, the primal attack uses Kannan’s embedding [53] and BKZ with block size \(\beta\), security estimates are obtained via the lattice estimator [54], [55]. These classical costs are far higher than our attack (Table 5).
For Falcon, Hawk, and NTRU, analogous BKZ estimates [40], [42], [45] hold. Hawk-256 (64-bit security) has BKZ block size \(\beta_{\rm BKZ}\approx250\) (\(\sim2^{73}\) classical gates). As a Module-LIP scheme, Hawk’s success threshold is the signature-norm bound \(\beta=\sigma_{\rm ver}\sqrt{8n}=47\), not a modulus \(q/2\). Our method achieves \(\gamma_{99\%}=73\) against this threshold, giving a formal margin of \(0.65\times\) (with safety factor \(\kappa=5\)) and an empirical margin of \(2.02\times\). Hawk-256 is the tightest case among all schemes considered.
Laarhoven [56] used quantum random walks to reduce the sieving exponent from \(2^{0.2075n}\) to \(2^{0.1327n}\). Chailloux and Loyer [20] gave a quantum speedup for BKZ’s SVP oracle, achieving block size \(\beta\) in \(2^{0.265\beta}\) quantum gates vs. \(2^{0.292\beta}\) classically. These are quadratic-root speedups and are already incorporated in NIST security levels [4]. For ML-KEM-1024, the reduction is from \(2^{243}\) to \(2^{220}\).
The original CDPR attack [9] has been refined. Cramer, Ducas, and Wesolowski [57], [58] used Stickelberger relations to improve the approximation factor from \(\exp(\tilde{O}(\sqrt{n}\log n))\) to \(\exp(\tilde{O}(\sqrt{n}))\). Our work reduces it further to \(\exp(O(\sqrt{\log n}))\), a qualitative improvement from super-polynomial to sub-polynomial.
Pellet-Mary, Hanrot, and Stehlé [59] gave a tradeoff: \(\gamma=\exp(\tilde{O}(\sqrt{n\cdot{}T_{\rm pre} / T_{\rm att}}))\). In the balanced regime this matches CDW [57], [58]. Our tower PIP makes both preprocessing and attack polynomial, achieving \(\gamma=\exp(O(\sqrt{\log n}))\) regardless of time allocation.
Felderhoff et al. [60] proved that Ideal-SVP remains hard for small-norm prime ideals \(\mathfrak{p}\) with \(\mathop{\mathrm{N}}(\mathfrak{p})=O(1)\), BKZ cannot do better than on random lattices. Our method succeeds for principal ideals generated by short elements, exploiting the unit group structure independent of the ideal’s norm.
Ducas, Espitau, and Postlethwaite [61] predicted module-BKZ quality, showing \(\delta_{\rm module}\le\delta_{\rm generic}^{1/d}\) for balanced modules. Chevignard et al [44] generalizes the rank-2 module-LIP attack to all number fields with at least one real embedding. Mureau et al. [62] attacked rank-2 module-LIP over \(2\)-power cyclotomic rings, recovering the secret isomorphism with a quantum algorithm using Biasse-Song PIP; it succeeds for \(n\le 64\).
SVP and CVP are NP-hard to approximate within \(n^{c/\log\log n}\) for some \(c>0\) [63], [64]. For constant approximation factors (e.g., \(\gamma\approx21\)), NP-hardness of exact SVP does not change, where the approximation regime is believed to be in BQP under GRH [31].
Whether Ideal-SVP is harder than generic SVP is open. Felderhoff et al. [60] showed Ideal-SVP is hard for prime ideals generated by small-norm elements. Our work shows principal ideals generated by short elements have \(\gamma_{}=O(\exp(\sqrt{\log n}))\).
Langlois and Stehlé [7] proved Module-LWE (and Module-SIS) is at least as hard as Ideal-SVP on module lattices. Albrecht and Deo [8] showed Ring-LWE with large modulus implies Module-LWE. These reductions are not tight for the sub-polynomial \(\gamma_{\rm CDPR}\).
The Biasse-Song algorithm [31] solves PIP in quantum polynomial time (under GRH, or unconditionally when \(h_k^+=1\)). No better quantum lower bound than BQP-hardness is known. Classically, the best PIP algorithms run in sub-exponential time \(L[1/2,c]\) [65]. For \(K=\mathbb{Q}(\zeta_{2^k})\), classical PIP costs \(2^{\Omega(\sqrt{n\log n})}\). Our tower PIP (Theorem 4) achieves \(O(n^3\log^2 n)\) quantum gates, an exponential quantum speedup.
This section steps back from the technical details to assess what the four-part series has collectively achieved and what remains open, as shown in Table 7. We presents a compact table comparing every key component of the original CDPR attack with Parts I-IV. The key is that the algebraic structure of 2-power cyclotomic rings can now be fully exploited by a quantum adversary: the approximation factor has been reduced from \(\approx 2^{54}\) to \(\approx 21\), and the PIP complexity from \(2^{\Omega(n)}\) to \(O(n^3\log^2 n)\) quantum gates (\(\sim 10^8\) for ML-KEM-1024).
| Component | Original CDPR | Parts I-IV |
|---|---|---|
| Class number \(h_k^+\) | Assumed=1 | Proved for \(k\le 12\) (Part I) |
| Module reduction | \(n^{O(d)}\) blowup | \(\alpha_d=O(1)\) (Part II) |
| SGP approx factor | \(\exp(\tilde{O}(\sqrt{n}))\) | \(\exp(O(\sqrt{\log n}))\) (Part III) |
| \(\sigma_{g_0}\) | \(\Theta(\sqrt{n})\) assumed | \(O(1)\), \(q\)-independent (Part III) |
| PIP complexity | \(2^{\Omega(n)}\) hidden | \(O(n^3\log^2 n)\) gates (Part IV) |
| \(\gamma\) (ML-KEM-1024) | \(\approx 2^{54}\) | \(\approx 21\) (median); \(\le 103\) (99%) (Part IV) |
Not all results in this series are unconditional. We identify every step where the proof relies on result from Parts I-III that is itself conditional, empirically, or numerically verified rather than proved in closed form. We state precisely which parts of the argument would need to be strengthened to obtain a fully rigorous unconditional result.
Acknowledgments will be added in the final version.