Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics Ming-Xing Luo School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China
arXiv:2605.17412v1 [quant-ph] 17 May 2026
May 19, 2026
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 = 1665 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(ζ8 ) ⊂ · · · ⊂ Q(ζ2k ) which yields a polynomial-time quantum algorithm costing O(n3 log2 n) gates, O(n2 log n) qubits, and 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.
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 unresolved: 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 Q(ζ2k ) for every k ≤ 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 αd = O(1) independent of module rank d.
1
√ • Part III. Computes the exact L2 CVP constant π/(2 6) for the log-unit lattice, shows the nearest lattice point is always the origin for short generators, and proves the per-component variance σg0 = O(1) regardless of the modulus q. • Part IV (this paper). Shows four parts combined can imply a probabilistic quantum algorithm costing O(n3 log2 n) gates, and γ ≤ 21 < q/2 for ML-KEM-1024, with 99% γ ≈ 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 γ 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 = 2k , n = 2k−1 = m/2, and ζ = e2πi/m . The 2k -th cyclotomic ring is defined by R = Z[ζ], the ring of integers of the cyclotomic field K = Q(ζ) [10, 11]. The Galois group Gal(K/Q) ∼ = (Z/mZ)× consists of all automorphisms σa : ζ 7→ ζ a for odd integers P a ∈ {1, 3, . . . , m − 1} [10]. The canonical embeddings are defined by σj : K ,→ C with σj (g) = i ci ζ ij , for odd j ∈ {1, 3, . . . , m − 1}. These evaluate the polynomial g at the n distinct primitive m-th roots of unity. There are n/2 independent embeddings. Q The field norm of g ∈ K is defined by NK/Q (g) = j odd σj (g) ∈ Z, and the trace is P TrK/Q (g) = j odd σj (g) ∈ Z. Both are integers for any g ∈ R [11, 12]. For a unit ε ∈ R× , we have | N(ε)| = 1.
2.2
Module lattices
A lattice Λ ⊂ Rm is a discrete additive subgroup, equivalently the set of all integer linear combinations of a basis {b1 , . . . , br } ⊂ Rm [13]. The minimum distance is defined by λ1 (Λ) = minv∈Λ\{0} ∥v∥2 , i.e., the length of the shortest nonzero vector. Finding λ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 ∼ = Rd embedded into Euclidean space via the canonical embeddings [14, 7]. A rank-d module lattice over R is determined by a matrix B ∈ Rd×d as ΛB = Bz :z ∈ Rd ⊂ K d . (1) Applying the embeddings σj entry-wise to every element of K d changes this into a classical Euclidean lattice of Z-rank nd, in Rnd . The secret key of ML-KEM [6] is a short vector (s1 , s2 ) ∈ Rk × Rℓ lying in a coset of the module lattice ΛA = (z1 , z2 ) ∈ Rℓ × Rk : Az1 + z2 ≡ 0 (mod q) . (2) Recovering (s1 , s2 ) from the public key (A, t) with t = As1 + s2 is precisely SVP on this module lattice. The hardness of this problem is established by Langlois and Stehlé [7]. 2
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 A ∈ Rqk×ℓ uniformly at random and t = As1 + s2 + e (mod q) for short secret and error vectors, it is computationally infeasible to recover (s1 , s2 , 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 v in the module lattice Λ with ∥v∥ ≤ γ λ̇1 (Λ), for the smallest achievable approximation factor γ. If γ < q/2 (for ML-KEM) or γ < q/β (for ML-DSA), the vector 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 2220 , 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 ∈ K, the log-embedding is defined by L(g) = log |σj (g)| odd j∈[1,m) ∈ Rn . The trace-zero projection can remove the overall scale as 1 ΠH0 (L(g)) = L(g) − log | NK/Q (g)| · 1 ∈ H0 , n P n where H0 = {x ∈ R : j xj = 0} is the trace-zero hyperplane.
(3)
(4)
The log-unit lattice is defined by Λ = {L(ϵ) : ϵ ∈ R× } ⊂ H0 . From the Dirichlet’s Unit Theorem [11] (with r1 = 0, r2 = n/2 for complex field K), Λ has rank r = n/2 − 1. The log-unit lattice encodes the unit group R× as a Euclidean lattice, converting the multiplicative problem of finding a short unit into the additive problem of CVP. Definition 2.2. For a nonzero g ∈ K, the log-embedding is given by L(g) = log |σ1 (g)|, log |σ3 (g)|, . . . , log |σn−1 (g)| ∈ Rn/2 .
(5)
As each conjugate embeddings has equal modulus, we denote one representative from each pair and then obtain a vector in Rn/2 . P ∈ Rn/2: i xi = 0} contains all log-embedded units as P The trace-zero hyperplane H0 = {x × j log |σj (ε)| = log | N(ε)| = 0 for ε ∈ R . Definition 2.3. For log-unit lattice Λ = L(R× ) ⊂ H0 , when h+ k = 1, a basis for Λ can be represented as the log-embeddings of the cyclotomic units ξa = sin(aπ/m)/ sin(π/m) for odd a ∈ {1, 3, . . . , n − 1} [10, 21]. Every unit ε ∈ R× maps to a point L(ε) in Λ. Two generators of the same ideal are different by a unit, i.e., if (g0 ) = (g), then g = g0 ε for some ε ∈ R× . So, we have L(g) = L(g0 ) + L(ε).
2.5
The Short Generator Problem
Definition 2.4. The Short Generator Problem (SGP) is defined by: Given a principal ideal I = (g) ⊂ R with a long generator g (potentially of exponentially large norm), find a short generator g0 such that (g0 ) = I and ∥g0 ∥2 is small. Since g = g0 ε, we have ΠH0 (L(g)) = ΠH0 (L(g0 )) + L(ε), where ΠH0 denotes orthogonal projection onto H0 . The problem of solving SGP is then reduced to CVP on Λ: The CVP solution L(ε) ∈ Λ identifies the unit discrepancy, and then g0 = g · ε−1 . 3
2.6
Babai’s nearest-plane algorithm
Babai’s nearest-plane algorithm [22, 18] 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 = (b1 , . . . , br ) with Gram-Schmidt orthogonalization (GSO) B ∗ = ∗ (b1 , . . . , b∗r ) [18], and a target t, Babai’s nearest-plane algorithm rounds the projection coefficients from i = r down to i = 1 as P ⟨t − j>i cj bj , b∗i ⟩ . (6) ci = ∥b∗i ∥2 P The output lattice vector is defined by v = i ci bi and the residual is ρ = t − v. The Coarse Lattice Theorem in Part III shows that for the specific targets arising from short ring generators, all rounding coefficients ci equal zero, so Babai algorithm outputs the zero vector and the residual is the target itself. The Infinite Capture Radius Theorem in Part III then shows that Babai algorithm can exactly recover an arbitrary lattice translation of such a target.
2.7
Module-LWE and ML-KEM security
The Module Learning With Errors (MLWE) problem over R with rank d, modulus q, and error distribution χ asks to distinguish between samples (A, As + e) and (A, u), where A ∈ Rqd×d , s, e ∈ Rqd are small, and u is uniform. ML-KEM’s security can be reduced to MLWE, which in turn reduced to Module-SVP with an approximation factor γ [7, 23]. An attacker who finds a vector of norm at most γ · λ1 (Λq ) in module lattice can distinguish MLWE samples [15, 7]. For full secret-key recovery, the attacker needs γ < q/2, i.e., the recovered vector should have coordinates small enough to be uniquely decoded modulo q by bounded-distance decoding [24, 9], see Table 1. Table 1: ML-KEM’s secure parameters.
3
Scheme
d
n
q
Attack threshold q/2
ML-KEM-512 ML-KEM-768 ML-KEM-1024
2 3 4
256 256 256
3329 3329 3329
1664.5 1664.5 1664.5
The Extended CDPR Algorithm
This section presents the full attack as a single Algorithm.
3.1
The four-phase structure
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 = g0 ε: the quantum phase finds some generator g of the ideal, but g may be exponentially larger than the shortest generator g0 . The classical phases recover the unit ε and divide it out. The approximation factor γ is the key quantity connecting the lattice attack to the cryptographic security of ML-KEM. Especially, our approximation factor is γ = ∥g0 ∥/∥gshort ∥ = exp(∥ρ∥∞ ),
4
(7)
√ where ρ is the CVP√residual. Parts II and III together show that ∥ρ∥∞ = O( log n), which implies γ = exp(O( log n)) ≪ nϵ for every ϵ > 0. For ML-KEM-1024 with n = 256, this evaluates to γtheory ≈ 21 at the median and γ99% ≈ 103, both far below the threshold q/2 = 1665. All symbols used in what follows are shown in Table 2. Here, note the difference between σj (an embedding of K) and σd (the intrinsic log-unit imbalance of the module determinant ideal), and between ρ (the CVP residual vector) and ψ ′ (the trigamma function). Table 2: All symbols used throughout the paper are collected in the table below. Symbol k≥3 m = 2k n = 2k−1 ζ = e2πi/m R = Z[ζ] K = Q(ζ) σj J = {1, 3, . . . , n − 1} Λ H0 ΠH 0 ψ′ ρ γ
3.2
Meaning Tower level index Conductor Ring degree = [K : Q] Primitive m-th root of unity Cyclotomic ring of integers Cyclotomic field Canonical embedding (j odd, 1 ≤ j ≤ m − 1) Representatives of conjugate pairs Log-unit lattice (rank r = n/2 − 1) Trace-zero hyperplane in Rn/2 Orthogonal projection onto H0 Trigamma function CVP residual vector SGP approximation factor = exp(∥ρ∥∞ )
The master algorithm
This subsection present the main algorithm shown in Algorithm 1 for the extended CDPR attack. Algorithm 1 Extended CDPR Attack on ML-KEM
INPUTS: B ∈ Rd×d : a module basis matrix for a rank-d Module-LWE instance over R = Z[ζ2k ] q: the ML-KEM modulus (e.g., q = 3329 for ML-KEM-1024) k ≤ 12: the tower level (h+ k = 1 by Part I) OUTPUT: A short generator g0 ∈ R of the determinant ideal (det B) ⊂ R, with approximation factor γ = exp(∥ρ∥∞ ) < q/2 PHASE 1: Module-to-Ideal Reduction (Part II) 1: Compute the Gram-Schmidt decomposition: B = QR · TR , where TR ∈ Rd×d is upper
triangular with principal ideals Ii = (TR,ii ) ⊂ R on the diagonal. 2: Set the determinant ideal I = I1 · I2 · · · Id = (det B) ⊂ R.
PHASE 2: Quantum Tower PIP (Section 5) 3: Recall the cyclotomic tower: Q ⊂ K3 ⊂ K4 ⊂ · · · ⊂ Kk = K. 4: for L = 3, 4, . . . , k do 5:
+ 1) Compute the norm ideal JL = NKL /K + (IL ) ⊂ RL , IL = I ∩ RL .
6:
+ 2) Set up an abelian HSP for the relative extension KL+ /KL−1 :
L
5
Algorithm 1 Extended CDPR Attack on ML-KEM
(continued)
L
Group: GL = (Z/NL Z)∆rL , NL = 2O(L·2 ) , ∆rL = 2L−3 new unit generators at level
7:
L. Q Oracle: fL (e1 , . . . , e∆rL ) = a ξaea mod IL+ (ring multiplication via NTT). 9: Run the quantum HSP algorithm: 10: (a) Prepare uniform superposition over GL . 11: (b) Query the oracle fL . 12: (c) Apply the QFT on GL . 13: (d) Obtain one element of HL⊥ . 14: (e) Repeat O(∆rL ) times to recover HL over Z. 15: 3) Extract the full integer relation matrix for the ∆rL new units. 16: 4) Obtain a generator gL of IL , stored in tower-factored form (Section 6). 17: end for 18: Set g ← gk . 8:
PHASE 3: Classical Log-Unit CVP (Part III) 19: Compute L(g) = (log |σj (g)|)j∈J ∈ Rn/2 via NTT-based polynomial evaluation [25, 26]. 2 20: Project t = ΠH0 (L(g)) = L(g) − ℓ̄ · 1, where ℓ̄ = n
P
j∈J log |σj (g)|.
//Run Babai’s nearest-plane algorithm on Λ// 21: Load the Gram-Schmidt basis B ∗ of the log-unit lattice Λ (from Part I). 22: Run Algorithm ?? with input (Λ, B ∗ , t). 23: Obtain the CVP output v ∈ Λ and residual ρ = t − v. PHASE 4: Short Generator P Recovery (Part III) ′ i di bi for integers di . Reconstruct the unit of ε = Q di × i ξai ∈ R , where ξai are the cyclotomic unit basis elements. 25: 2) Compute g0 = g · (ε′ )−1 . 26: 3) Compute γ = exp(∥ρ∥∞ ) and verify γ < q/2. 27: if γ ≥ q/2 then 28: Retry with a different basis ordering (probability < 0.10 of failure for d = 4). 29: end if 30: return g0 , γ. 24: 1) Solve the linear system v =
We now explain every major component of Algorithm 1 in detail. The module decomposes into ideals: The start of this phase is a module basis matrix B ∈ Rd×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 = QR · TR , where TR ∈ Rd×d is upper triangular (with diagonal entries in R \ {0}) and QR accounts for the change of basis. The diagonal entries TR,ii generate the successive layer ideals Ii = (TR,ii ) ⊂ 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 cyclotomic tower: The quantum phase works level by level according to the cyclotomic tower Q ⊂ K3 ⊂ · · · ⊂ Kk . At each level L, the field KL is a quadratic extension of KL−1 , i.e., [KL : KL−1 ] = 2. This implies each new level L contributes ∆rL = 2L−3 new unit generators (Lemma 5.1). By working level by level, it requires to deal with ∆rL new units at each step. As ∆rL grows linearly with L, the quantum HSP at each level is small. Step 1) Norm descent. The CM structure of KL means every unit can be decomposed into a totally real part and a root of unity. Taking the norm NKL /K + collapses the ideal IL ⊂ RL to a L
6
+ smaller ideal JL ⊂ RL in a field of half the degree. Since h+ = 1, the smaller ideal is principal. K+ L
So, finding its generator is a PIP problem in a smaller field which can be solved recursively. Step 2) Quantum HSP. The ∆rL new unit generators at level L can be found by solving + the Abelian Hidden Subgroup Problem (HSP) for the extension KL+ /KL−1 . Here, the HSP encodes the integer relations among a generating set of candidate units, i.e., the hidden subgroup HL 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 HL⊥ . After O(∆rL ) repetitions, we get enough samples to recover HL . Steps 3)-4): Classical relation and generator recovery. The measurements in HSP give a matrix of samples from HL⊥ . Using classical LLL lattice reduction, we can find the integer relation lattice HL , which identifies the new unit generators. Combining these with the norm generator from Step 1), we get a generator gk of the full ideal I, which is stored in tower-factored form (Section 6). Computing the log-embedding: With the generator g of the ideal, we then compute its log-embedding L(g) ∈ Rn/2 . In the power basis, this requires to evaluate a degree-n polynomial with huge coefficients at each embedding σj . This might have potentially exponential cost. Instead, with tower-factored form of g, Proposition ?? shows log |σj (g)| can be computed in O(n2 log2 n) bits from the factored representation. As the projection ΠH0 removes the mean ℓ̄ from all coordinates, we subtracts a vector proportional to 1, which corresponds to removing the overall scale of g as the CVP distance is scale-independent. Babai’s algorithm on the log-unit lattice: From Algorithm ??, the log-unit lattice Λ has rank r = n/2 − 1, embedded in the (n/2 − 1)-dimensional space H0 . Its Gram-Schmidt √ basis vectors b∗i have norms ∥b∗i ∥2 = Ω( n), which are much larger than the per-component fluctuation (variance) σt = O(1) of the target t. This implies every projection coefficient √ µi = ⟨t, b∗i ⟩/∥b∗i ∥2 has magnitude O(1/ n) ≪ 1/2. So. we have ci = ⌊µi ⌉ = 0 for any i. Thus, Babai’s algorithm returns v = 0 for short generators. For the real PIP output g = g0 ε, the target is given by t = ΠH0 (L(g0 )) + L(ε), i.e., a shift of the balanced target by a lattice vector L(ε) ∈ Λ. Babai’s back-substitution (Infinite Capture Theorem in 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(ε) regardless of its size. Short generator recovery: The CVP output v = L(ε) is the log-embedding of the unit P discrepancy. We recover ε by solving for the integer exponents di in v = i di bi , and then form Q ˙ ′ )−1 . the product ε′ = i ξadii . This gives the short generator as g0 = g (ε The approximation factor is given by γ = exp(∥ρ∥∞ ), where the residual ρ = t − v = ΠH0 (L(g0 )). By L∞ Bound Theorem (Part III), we get √ √ ∥ρ∥∞ = σd 2 ln n + O( ln ln n), (8) √ which implies γ = exp(O( log n)) ≪ nϵ for every ϵ > 0.
4
Approximation Gap Closure
This section answers whether the resulting approximation factor γ is small enough to break ML-KEM.
7
4.1
The main approximation theorem
Theorem 4.1. Let R = Z[ζ2k ] with n = 2k−1 ≥ 8 and k ≤ 12. For a rank-d Module-LWE instance with modulus q and a randomly generated secret key, Algorithm 1 achieves a Module-SVP approximation factor as √ γ = αd · exp(σd 2 ln n) · (1 + o(1)), (9) √ where αd = C is the module-reduction factor (Part II), q with C ≤ 1.36 for MLWE-distributed P inputs. The worst-case analytic bound is C ≤ 3.10; σd = 14 dj=1 ψ ′ (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 (i) med(γ) < q/2 for all standardized ML-KEM parameter sets; (ii) Pr[γ < q/2] > 0.99 for d ≤ 3; (iii) Pr[γ < q/2] ≥ 0.90 for d = 4; (iv) With O(log(1/δ)) independent repetitions, the attack succeeds with probability ≥ 1 − δ. Proof. The Gram-Schmidt decomposition of B over R in Algorithm 1 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 L2 norm of the diagonal entry of TR 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 ≤ 1.36 with a probability larger than 0.99 at n = 256. The module-reduction factor is αd = C ≤ 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 ΠH0 (L(g0 )) as d X 1 2 2 p 1 σd = ∥ΠH0 (L(g0 ))∥2 → − ψ ′ (j) n 4 j=1
(10)
when n → ∞. The variance σd2 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 γ = exp(∥ρ∥∞ ), where ρ = ΠH0 (L(g0 )) is the CVP residual. This is a vector in Rn/2 with i.i.d. (asymptotically) coordinates, each with variance σd2 . By Part III, the maximum of n/2 such coordinates satisfies √ √ ∥ρ∥∞ = σd 2 ln n + O( ln ln n), (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 ψ ′ (1) = 2 π /6 ≈ 1.6449, ψ ′ (2) ≈ 0.6449, ψ ′ (3) ≈ 0.3949, and ψ ′ (4) ≈ 0.2838. The tail probability is from the sub-Gaussian concentration of ∥ρ∥∞ . pFor γ > q/2, the exponent would need to exceed ln(q/(2αd )) ≈ 7.26, while its median is σd 2 ln(n/2) ≈ 2.69. The gap of ≈ 4.6 is more than 5× the per-component standard deviation σ4 = 0.861, and in units of the Gumbel fluctuation scale σG ≈ 0.28. For d = 4, in actual ring model with n = 256, Monte Carlo simulation (105 trials with both uniform mod-q and CBD (η = 2) coefficient distributions) confirms the Gaussian-model prediction, we get zero failures. The largest empirical γ across all trials gives an empirical 99% γ99% ≈ 103, which is still below q/2 = 1665. For d ≤ 3, both the Gaussian analysis and simulation give Pr[γ > q/2] < 10−3 . 8
Table 3: √ Approximation factor bounds for ML-KEM (n = 256, q = 3329). γtheory = αd · exp(σd 2 ln n), γ99% = 5γtheory (105 -trial simulations with mod-q coefficient distributions). Scheme
d
σd
γtheory
γmed
γ99%
Median margin
99% margin
ML-KEM-512 ML-KEM-768 ML-KEM-1024
2 3 4
0.757 0.819 0.862
14.5 17.9 20.6
9.6 11.4 12.9
73 90 103
173× 146× 129×
23× 19× 16×
In all cases, using O(1) independent repetitions with fresh basis orderings can reduce the per-attack failure probability below 10−6 (Section 4.2). We use the threshold γ < 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, . . . , (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 σnoise = 1 might give a more restrictive threshold γ ≲ q/(c σnoise dn) with a constant c [24, 7]. ∗ Table 1 (Part III) confirms that the ratio monotonically with n and is p σt / mini ∥bi ∥ decreases π consistent with the theoretical rate Θ(1/ n/ log n), where σt = 2√ 0.64 is the per-component ≈ 6 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 (σt / mini ∥b∗i ∥ ≤ 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.
4.2
Tail analysis and repetition strategy
For d = 4, the empirical median is γmed ≈ 12.9 with γ99% ≈ 103 and zero failures in 105 simulation trials. All values lie far below the threshold q/2 = 1665. 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 4.2. For a random rank-d MLWE module over R with i.i.d. bounded coefficients, the empirical median, γ99% , and success probabilities are given in Table 4, based on 105 -trial ring simulations at n = 256.
Table 4: Empirical tail statistics for ML-KEM (n = 256, q = 3329), from 105 -trial simulations with mod-q coefficient distributions. d
med(γ)
γ99%
Pr[γ < q/2]
99% margin to q/2 = 1665
2 3 4
9.6 11.4 12.9
73 90 103
> 0.999 > 0.999 > 0.999
23× 19× 16×
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 ∈ J (|J| = n/2 = 128), the matrix σj (B) ∈ Cd×d has asymptotically i.i.d. CN (0, nσc2 ) entries [29]. For such a random matrix, the smallest singular value smin satisfies [30]: Pr[smin < ϵτ ] ≈ (dϵ)2 9
for small ϵ,
(12)
where τ 2 = nσc2 . The Gaussian-model tail probability for the L∞ norm exceeding the threshold T = ln(q/(2αd )) ≈ 7.3 is dominated by the sub-Gaussian tail of the maximum of n/2 coordinates, p each with variance σd2 . The median of ∥ρ∥∞ is σd 2 ln(n/2) ≈ 2.7, and the gap to the threshold is T − 2.7 ≈ 4.6, which exceeds 5 standard deviations of σ4 . Under the Gaussian model, Pr[∥ρ∥∞ > T ] < 10−7 for all d ≤ 4. Empirical finite-n distribution. We implement ring simulation with n = 256 confirms the Gaussian prediction, i.e., output zero failures across 105 trials at d = 4 with both uniform mod-q and CBD (η = 2) coefficient distributions. The empirical distributions are d=2:
γmed = 9.6,
γ99% = 73,
γmax ≤ 200;
d=3:
γmed = 11.4,
γ99% = 90,
γmax ≤ 200;
d=4:
γmed = 12.9,
γ99% = 103,
γmax ≤ 200.
The γ99% is approximately 5× the median in all three cases, shows the heavy tail induced by occasional near-zero embeddings of det(σj (B)). However, even in the worst observed cases, γ remains below q/2 = 1665. For d = 4, with one independent repetition (using a different basis ordering), the probability that both attempts produce γ > q/2 is empirically below 10−6 . When γ > 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.
5
The Polynomial Tower PIP Algorithm
The quantum phase of Algorithm 1 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.
5.1
The coefficient explosion and GRH
P i A unit ε ∈ Rk× in the standard power basis is represented by ε = n−1 i=0 ai ζ with ai ∈ Z. The fundamental units are cyclotomic units ξa = sin(aπ/m)/ sin(π/m) for odd a [10, 21]. A general unit is a product as Y ε= ξaea , (13) a odd
where the exponents ea ∈ 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 2O(n) bits. Meanwhile, the Biasse-Song algorithm requires generalized Riemann hypothesis (GRH) for number fields of degree up to n = 256 [31].
5.2
The cyclotomic tower structure
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 Q ⊂ K3 = Q(ζ8 ) ⊂ K4 = Q(ζ16 ) ⊂ · · · ⊂ Kk = Q(ζ2k ), where [KL : KL−1 ] = 2 for every L ≥ 4. 10
(14)
Lemma 5.1. For all L ≥ 3, the following results hold (i) [KL : KL−1 ] = 2; × (ii) rk(RL ) = 2L−2 − 1; × × (iii) ∆rL := rk(RL ) − rk(RL−1 ) = 2L−3 for L ≥ 4, and ∆r3 = 1; × + × (iv) ker(NKL /K + : RL → (RL ) ) = µ2L (finite torsion of order 2L ); L
+ (v) All ∆rL new free unit generators at level L lie in the totally real subtower KL+ /KL−1 .
Proof. Part (i) is from ζ22L = ζ2L−1 , so ζ2L satisfies the quadratic x2 − ζ2L−1 ∈ KL−1 [x], which is irreducible as ζ2L ∈ / KL−1 . Part (ii) is from the Dirichlet’s Unit Theorem [11, 12] with r1 = 0 and r2 = 2L−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 rk(RL ) = rk((RL ) ). So, the CM kernel has rank 0 and all free units come from the real subfield. Definition 5.2. A unit ε ∈ Rk× is in tower-factored form if it is stored as a product of relative units across the tower as ε = ε3 · ε4 · · · εk ,
× × εL ∈ RL /RL−1 ,
(15)
where each εL is stored as a linear polynomial εL = aL + bL ζ2L with aL , bL ∈ RL−1 , themselves in tower-factored form for the (L − 1)-level tower. Proposition 5.3. A unit in tower-factored form has total storage size O(n2 log n) bits, and evaluation cost O(n2 log2 n) bit operations for any single log-embedding log |σj (ε)|. Proof. At level L, the factor εL has nL = 2L−1 leaf integers, each requires O(L · 2L ) bits. Storing at level L then costs O(nL · L · 2L ) = O(L · 22L−1 ). So, we get for all L levels k X
O(L · 22L ) = O(k · 22k ) = O(n2 log n).
(16)
L=3
Q Here, our evaluation uses the multiplicative structure of σj (ε) = kL=3 σj (εL ), where each factor 2 L 2 2L costs O(n operations from fast integer multiplication [33]. The total PkL · L · 22 ) =2LO(L · 2 2 ) bit cost is L=3 O(L · 2 ) = O(k · 22k ) = O(n2 log2 n). The tower-factored form stores a unit as a product of relative factors ε = ε3 · · · εk . We obtain × from ε · ε′ per-level products εL · ε′L , which are elements of RL 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 εL ∈ RL /RL−1 .
5.3
The tower PIP algorithm
We now state the main complexity theorem and complete quantum algorithm. Theorem 5.4. Given a principal ideal I ⊂ Rk with h+ k = 1 and k ≤ 12, there exists a quantum algorithm (Algorithm 2) generating a generator g with (g) = I, using O(n3 log2 n) quantum gates, O(n2 log n) qubits, and O(n5+ϵ ) classical bit operations. Algorithm 2 Polynomial Tower PIP
INPUTS: I ⊂ Rk : a principal ideal, given by a Z-basis k ≤ 12: the tower level (h+ k = 1, Part I) OUTPUT:
11
Algorithm 2 Polynomial Tower PIP
(continued)
g ∈ Rk : a generator of I, i.e., (g) = I, stored in tower-factored form (Definition 5.2) BASE CASE (L = 3): K3 = Q(ζ8 ), degree n3 = 4, unit rank √ r3 = 1 −1 1: Compute the unit ξ3 = ζ8 + ζ8 = 2. 2: Compute I3 = I ∩ R3 . 3: Find e such that I3 = (ξ3e ) by rounding: e = ⌊logξ3 N(I3 )/2⌉. 4: Set g3 ← ξ3e , stored as the integer pair (e, 0) in tower-factored form. INDUCTIVE STEP: for L = 4, 5, . . . , k (Assume PIP for KL−1 has been solved; solve for KL .) 5: for L = 4, 5, . . . , k do 6:
Step 1: + Compute the norm ideal: JL = NKL /K + (IL ) = IL · IL ⊂ RL . L
7: 8:
9: 10:
Solve PIP for JL in KL+ recursively using real subtower K3+ ⊂ · · · ⊂ KL+ . + Obtain a generator gL+ ∈ RL of JL , stored in tower-factored form. Step 2: Set the precision: bL ← ⌈10 · L · 2L ⌉ bits. Enumerate ∆rL = 2L−3 new relative units at level L: UL = {ξa : a odd, 2L−2 < a < 2L−1 }
11: 12: 13:
Set HSP group: GL = (Z/2bL Z)∆rL , encoding integer exponent vectors for new units. Quantum subroutine: Initialize ∆rL quantum registers, each of bL qubits, in uniform superposition: X 1 |ψ0 ⟩ = √ |e1 , . . . , e∆rL ⟩|0⟩. (18) 2bL ∆rL (e1 ,...,e )∈G ∆rL
14:
(17)
L
+ + /IL defined by Query quantum oracle fL : GL → RL Y fL (e1 , . . . , e∆rL ) = ξaea mod IL+
(19)
a∈UL
15: 16: 17:
18: 19: 20: 21:
22:
which is implemented using NTT-based ring multiplication [25]. Apply the QFT on each register of GL . Measure the first register; obtain one sample s ∈ HL⊥ , where HL = ker(fL ). Repeat lines 11-16 Nrep = O(∆rL ) times to collect samples s1 , . . . , sNrep ∈ HL⊥ . Step 3: Reshape the sample matrix SL ∈ ZNrep ×∆rL with rows s1 , . . . , sNrep . Run LLL lattice reduction on the kernel lattice of SL to recover a full basis for HL . Extract ∆rL integer relation vectors h1 , . . . , h∆rL from the LLL basis. Q (h ) × Check a∈UL ξa j a ∈ RL−1 for each j, products are units in previous level’s ring. Step 4: Solve discrete logarithm problem as: + + × find d ∈ Z∆rL such that NKL /K + (gLcandidate ) = gL+ · u+ L for some uL ∈ (RL−1 ) . L
× × Construct: gL = gL−1 · εL , εL ∈ RL /RL−1 is a relative unit correction from Step 3. 24: Verify (gL ) = IL by checking ideal equality in RL . 25: end for
23:
26: return g ← gk , stored in tower-factored form.
12
5.4
Correctness
We show Algorithm 2 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 R3 = Z[ζ8 ] has rank 1, generated by 2 up to torsion µ8 . The ideal I3 = (ξ3e ) for a unique e determined by N(I3 ) = 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 JL = NKL /K + (IL ) is a principal ideal in RL as h+ = 1 (Part I). The K+ L
L
recursion on the totally real subtower finds gL+ correctly by the inductive hypothesis applied to KL+ . • Step 2: The hidden subgroup HL encodes integer relations among the generating set UL . The abelian HSP algorithm [34, 1] can find HL⊥ , and recover HL with probability 1 − 2−Ω(∆rL ) from O(∆rL ) samples. • Step 3: The precision bL = O(L · 2L ) exceeds the logarithm of the determinant of the relation sublattice HL ⊂ GL , such that LLL algorithm can find the full relation basis [16]. • Step 4: The discrete logarithm over Z can be solved in polynomial time. The output gL satisfies (gL ) = IL by construction. By induction, the algorithm is correct for all L ≤ k. Now, we estimate the complexity. At level L, the dominant costs are given by Quantum gates : O(∆rL ) · O(nL log nL · ∆rL ) = O(22(L−3) · 2L−1 · L) = O(L · 23L−7 ), Qubits : ∆rL · bL = O(2L−3 · L · 2L ) = O(L · 22L−3 ), 5 Bit operations : O(∆rL · b2L ) = O(25(L−3) · L2 · 22L ) = O(L2 · 27L−15 ).
As it is dominated by the top level L = k, we obtain the total costs as Qtotal =
k X
O(L · 23L ) = O(n3 log n),
(20)
L=3
Nqubits = O(k · 22k ) = O(n2 log n), Cbit =
k X
O(L2 · 27L ) = O(n7 log2 n)
(21) (22)
L=3
with n = 2k−1 and k = O(log n). The O(n3 log2 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(n5+ϵ ) using the L2 algorithm [36].
5.5
ML-KEM-1024
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 ≈ 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., ∆r9 = 64 new relative units and 64 independent HSP runs, each using NTT-based ring multiplication [25] as the oracle. Table 5 summarizes all costs.
13
Table 5: Quantum resource cost for analyzing ML-KEM-1024 (k = 9, n = 256). The total logical-gate cost is dominated by the top level (L = k), where the per-level cost is O(L2 · 23L−6 ). Resource
Estimated Value
New units at top level (∆r9 ) HSP repetitions at top level Oracle gates per HSP call (NTT, n = 256) Per-HSP QFT cost (top level) Total logical gates (top level) Total logical gates (all levels) Logical qubits Physical qubits (surface code, d = 30, 10−15 error) Physical gate operations
6
64 64 ≈ 2048 ≈ 2 × 104 ≈ 9 × 107 ≈ 227 ≈ 1400 ≈ 1.4 × 106 ≈ 237
Extensions to Other Lattice Schemes
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 Z[ζ2k ]. Specially, we analyze Falcon [39], Hawk [40], and NTRU over 2-power cyclotomics [41, 42].
6.1
Formal sufficiency theorem
We state three algebraic conditions (A1)-(A3), together with a sufficiency theorem asserting that they are all that is needed to run our attack. (A1) Trivial plus-class number. The maximal totally real subfield K + = Q(ζ2k )+ satisfies hK + = 1, i.e., every ideal of OK + is principal. This holds for every k ≤ 12 (Part I). (A2) Binary cyclotomic tower. The field K = Q(ζ2k ) is at the top of the tower Q ⊂ K3 ⊂ K4 ⊂ · · · ⊂ Kk = K, where each step is a quadratic extension. By Lemma 5.1, this holds for any k ≥ 3. (A3) Trigamma variance formula. For the rank-d module determinant ideal generated by a random module matrix B ∈ Rd×d with i.i.d. centered coefficients of finite fourth moment, the per-component variance of the log-embedding of the shortest generator satisfies d X 2 p 1 σd → − ψ ′ (j) 4 j=1
as n → ∞,
(23)
where ψ ′ is the trigamma function (Part III). Theorem 6.1. Let Π be a lattice-based cryptographic scheme whose key-recovery problem reduces to Module-SVP or to PIP (e.g. via Module-LIP [43]) over the ring R = Z[ζ2k ] with k ≤ 12 and effective module rank d. Suppose conditions (A1), (A2), and (A3) hold. Then Algorithm 1 applies to Π and achieves the approximation factor as √ γ = αd · exp(σd 2 ln n) · (1 + o(1)), (24) q P √ where αd = C with C ≤ 1.36 for module-distributed inputs (Part II), and σd = 14 dj=1 ψ ′ (j) from (A3). Attack success probability and tail bounds are shown as in Theorem 4.1. 14
Proof. Theorem 4.1 shows Eq.(24) 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 2), 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 Π.
6.2
Falcon
Falcon [39], slated for standardization as FIPS 206 (FN-DSA) [44], is a hash-and-sign signature scheme based on the GPV framework [45]. It uses the ring R = Z[ζ2n ] = Z[x]/(xn + 1) with n ∈ {512, 1024} and prime modulus q = 12289. The public key is a rational function h = g · f −1 mod q, where (f, g) ∈ R2 is a short pair of ring elements satisfying ∥f ∥22 + ∥g∥22 ≈ q. The corresponding NTRU lattice is defined by Λh = {(u, v) ∈ R2 : u + vh ≡ 0
(mod q)},
(25)
which has a short basis (f, g; F, G) satisfying the NTRU equation f · G − g · F = q in R. The security of Falcon’s key-recovery has been reduced to the Short Basis Problem (SBP) for Λh [45]: given only h, find a short basis of Λh . The SBP can be further reduced to the SGP for the determinant ideal of Λh . Lemma 6.2. Let Λh be Falcon NTRU lattice and I = (det Λh ) = (q) ⊂ R be its determinant ideal. Any short basis (f, g; F, G) of Λh satisfies f · G − g · 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 × 2n integer basis matrix of Λh formed by the rows of (f, g) and (F, G) in coefficient-vector form. Its determinant is | det Λh | = q n , as an ideal norm. Since every ideal of R is principal under condition (A1), the ideal (q n ) has a generator g0 = f · G − g · F . Solving the NTRU equation yields g0 = q. From a short pair (f, g) we can identify both a short generator of ideal (q) ⊂ R and the full short basis. Using the extended Euclidean algorithm over R, it costs O(n2 ) ring operations [16]. Proposition 6.3. Both Falcon parameter sets satisfy conditions (A1), (A2), and (A3). Proof. (A1) Falcon-512 uses ζ1024 , corresponding to k = 10 while Falcon-1024 uses ζ2048 , + corresponding to k = 11. By Part I, we have h+ 10 = 1 and h11 = 1 unconditionally. Hence, every ideal in the totally real subring OK + is principal, which implies the norm-descent step of Algorithm 2 produces a principal ideal. (A2) The ring R = Z[ζ2n ] for n ∈ {512, 1024} is the 2-power cyclotomic ring of Lemma 5.1, with m = 2n = 2k and k ∈ {10, 11}. Note the cyclotomic tower Q ⊂ Q(ζ8 ) ⊂ · · · ⊂ Q(ζ2n ) has k − 2 levels, each a quadratic extension. We can apply Algorithm 2. (A3) The Falcon NTRU lattice Λh is a rank-2 module over R. Its determinant ideal is (q) ⊂ R, and q is a rational integer whose log-embedding projects to 0 ∈ H0 as all embeddings of a rational integer have equal modulus. So, we have the determinant ideal σ(q) = 0. In this case, we extend CDPR to target the first Gram-Schmidt ideal (f ) ⊂ R, where f is a random ring element with i.i.d. centered coefficients of variance σf2 from a discrete Gaussian distribution [39]. Since f is a single random ring element, the Trigamma rank is d = 1, which then gives π2 1 ≈ 0.4112, σ12 = ψ ′ (1) = 4 24
σ1 ≈ 0.641.
(26)
p As a conservative upper bound, we may use the generic rank-2 formula σ2 = [ψ ′ (1) + ψ ′ (2)]/4 ≈ 0.757, bounding the worst-case Gram-Schmidt layer of any rank-2 module. Both values are used in Theorem 6.4, where σ1 gives the tighter bound for the real attack, while σ2 provides a safe upper bound. 15
Theorem 6.4. For Falcon-n with n ∈ {512, 1024} and q = 12289, the Algorithm 1 applied to the NTRU lattice Λh achieves the approximation factor as √ γn = α2 · exp σ2 2 ln n · (1 + o(1)), (27) where σ2 = 0.757 and α2 ≤ 1.17. Simulation gives explicit values as √ Scheme 2 ln n γtheory γ99% Margin Falcon-512 Falcon-1024
3.53 3.72
16.9 19.6
85 98
≤ 72 ≤ 63
All values satisfy γ99% ≪ q/2 = 6145. Proof. Proposition 6.3 verifies conditions (A1)-(A3) for both Falcon parameter sets. Theorem 6.1 applies with d = 2 and σ = σ1 (first GS layer, corresponding to the ideal (f )) or σ = σ2 (conservative bound over both GS layers). Proposition 6.5. Given the short generator g0 recovered by Algorithm 1, the complete Falcon secret key (f, g, F, G) can be reconstructed in polynomial classical time. Proof. By Lemma 6.2, a short generator of (q) in R is the element f · G − g · F = q. From the output g0 ≈ 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 ≡ f · h (mod q) directly from the public key h. Second, we solve NTRU equation f · G − g · F = q by the extended Euclidean algorithm√over R, costing O(n2 log n) bit operations [16] and returning (F, G) satisfying ∥F ∥∞ , ∥G∥∞ = O( q log n). The recovered key can pass the validity check with a probability 1 − exp(−Ω(n)) whenever γ < q/2.
6.3
Hawk
Hawk [40] is a lattice signature scheme over the 2-power cyclotomic ring R = Z[x]/(xn + 1) with n ∈ {256, 512, 1024}. The secret key is a basis B ∈ R2×2 for Z2n 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 ∗ · B, and the verification bound is the Q-norm 2 ⟨s, Qs⟩ ≤ σverify · 8n, (28) √ i.e., the signature norm is bounded by βHawk = σverify 8n, where σverify takes the values 1.042, 1.425, 1.572 for Hawk-256/512/1024 respectively. Note only Hawk-512 (NIST Level 1) and Hawk-1024 (NIST Level 5) are official parameter sets.
Lemma 6.6. [43] Given the Hawk public key h = g · f −1 ∈ R2 (where R2 = R/2R), recovering the secret key (f, g, F, G) is polynomial-time equivalent to solving the PIP for the principal ideal (f ) ⊂ R in the ring R = Z[ζ2n ]. Proposition 6.7. For n ∈ {256, 512, 1024}, conditions (A1)-(A3) for the CDPR attack hold: (A1) h+ k = 1 for the corresponding conductors k ∈ {9, 10, 11} by Part I; (A2) The 2-power cyclotomic tower applies directly, n = 2k−1 ; (A3) The PIP target (f ) has f sampled from a centered binomial distribution. As Hawk’s NTRU-equation f · G − g · F = 1 effectively gives a rank-2 short-vector problem, so we use the conservative d = 2 bound σ2 = 0.7566. Theorem 6.8. The present extended CDPR method applied to the PIP target (f ) (Lemma 6.6) emp formula with γ formula = 5γ achieves the margin βHawk /γ99% theory , and the empirical margin βHawk /γ99% 99% from a 105 -trial i.i.d.-Gaussian and max simulation as 16
Scheme †
Hawk-256 Hawk-512 Hawk-1024
n
σv
βHawk
γtheory
formula γ99%
emp γ99%
Margin formula
Margin emp
256 512 1024
1.042 1.425 1.572
47 91 142
14.5 16.9 19.6
73 85 98
23 26 29
0.65× 1.08× 1.45×
2.02× 3.47× 4.84×
† HAWK-256 is conditionally broken: the median attack succeeds (γ theory = 14.5 < β = 47), and the i.i.d Gaussian simulation succeeds in 99.99% of 105 trials. While the formal κ = 5 upper formula = 73 exceeds the threshold β = 47, classifying it as not broken under the most bound γ99% conservative measure.
Hawk’s margins √ are much tighter than those of ML-KEM or Falcon as the signature-norm bound β = σverify 8n is far smaller than a typical modulus q/2. Proposition 6.9. Given the short generator f0 recovered by Algorithm 1, the full Hawk secret key (f, g, F, G) is reconstructed in O(n2 log n) classical bit operations. Proof. By Lemma 6.6, f0 is the shortest generator of the ideal (f ) ⊂ R. Compute g0 = f0 · h mod 2. Solve f0 · G0 − g0 · F0 = 1 by using the extended Euclidean algorithm over R [43]. The solution exists as gcd(f0 , g0 ) = 1 in R. This is from the NTRU equation f · G − g · F = 1 and f0 ≈ f .
6.4
NTRU over 2-power cyclotomics
NTRU [46] over the 2-power cyclotomic ring R = Z[x]/(xn + 1) uses the same NTRU lattice (25) as Falcon: (i) it uses different parameter ranges for (f, g), and (ii) the NIST-standardized variants (NTRU-HPS and NTRU-HRSS) use R′ = Z[x]/Φ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 6.10. For NTRU over R = Z[x]/(xn + 1) with n = 2k−1 , k ≤ 11, and q a prime, all conditions (A1), (A2), and (A3) hold. Proof. (A1) For k ≤ 11, we have h+ k = 1 from Part I. (A2) As the ring R = Z[ζ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[fi = 1] = Pr[fi = −1] = d/(2n) and Pr[fi = 0] = 1 − d/n for a weight parameter d. The mean is 0, the variance is σf2 = d/n, and the fourth moment is finite. We can apply condition (A3) with drank = 2 (NTRU is a rank-2 module), which gives σ2 ≈ 0.757 independent of d and q. • NTRU-HRSS: The element f = f1 · f2 for small f1 , f2 ∈ 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 σf2 = σf21 σf22 n [28]. So, this condition holds with the same σ2 ≈ 0.757.
Theorem 6.11. For the four standardized NTRU-HPS/NTRU-HRSS parameter sets (which use prime-conductor cyclotomic rings Z[ζp ]; see Part V for the complete analysis), the extended CDPR attack achieves √ γ = α2 · exp(σ2 2 ln n) · (1 + o(1)), (29) with σ2 ≈ 0.757 and α2 ≤ 1.17. The numerical values are given by 17
Scheme
p
n = p−1
q
γtheory
γ99%
Margin
NTRU-HPS-2048-509 NTRU-HPS-2048-677 NTRU-HPS-4096-821 NTRU-HRSS-701
509 677 821 701
508 676 820 700
2048 2048 4096 8192
16.9 18.0 18.7 18.1
85 90 94 91
12.1× 11.4× 21.9× 45.2×
The class-number condition h+ p = 1 for each NTRU prime is verified unconditionally in Part V. Proposition 6.10 verifies conditions (A1)-(A3). From Theorem 6.1 we get the formula. The NTRU attack of Kirchner and Fouque [47] 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 γ = O(exp( 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. √ Table 6: Approximation factors for all 2-power cyclotomic schemes. γtheory = αd exp(σd 2 √ ln n) with αd = 1.17. γ99% = 5γtheory (validated by 105 -trial simulation). Hawk uses β = σverify 8n as threshold. NTRU uses real NTRU-HPS/HRSS parameters (Part V). Scheme
Family
d
n
q
γtheory
γ99%
Threshold
Margin
ML-KEM-512 ML-KEM-768 ML-KEM-1024
Module-LWE Module-LWE Module-LWE
2 3 4
256 256 256
3329 3329 3329
14.5 17.9 20.6
73 90 103
1665 1665 1665
23× 19× 16×
Falcon-512 Falcon-1024
NTRU-GPV NTRU-GPV
2 2
512 1024
12289 12289
16.9 19.6
85 98
6145 6145
72× 63×
Hawk-256† Hawk-512 Hawk-1024
Module-LIP Module-LIP Module-LIP
2 2 2
256 512 1024
– – –
14.5 16.9 19.6
73 85 98
β=47 β=91 β=142
0.65× 1.08× 1.45×
NTRU-HPS-2048-509 NTRU-HPS-2048-677 NTRU-HPS-4096-821 NTRU-HRSS-701
NTRU NTRU NTRU NTRU
2 2 2 2
508 676 820 700
2048 2048 4096 8192
16.9 18.0 18.7 18.1
85 90 94 91
1024 1024 2048 4096
12× 11× 22× 45×
†
7
Empirical margin 2.02× > 1 under κemp ≈ 1.6.
Comparison with Recent Results
The best classical attacks on lattice problems rely on the BKZ algorithm [17, 18] and its variants [48, 49], often combined with sieving [50, 51, 19]. The fastest classical sieving solves SVP in dimension n in time and space 20.2075n+o(n) [19]. For Module-LWE, the primal attack uses Kannan’s embedding [52] and BKZ with block size β, security estimates are obtained via the lattice estimator [53, 54]. These classical costs are far higher than our attack (Table 5). For Falcon, Hawk, and NTRU, analogous BKZ estimates [44, 40, 42] hold. Hawk-256 (64-bit security) has BKZ block size βBKZ ≈ 250 (∼ 273 classical gates). √ As a Module-LIP scheme, Hawk’s success threshold is the signature-norm bound β = σverify 8n = 47, not a modulus q/2. Our method achieves γ99% = 73 against this threshold, giving a formal margin of 0.65× (with safety factor κ = 5) and an empirical margin of 2.02×. Hawk-256 is the tightest case among all schemes considered. 18
Laarhoven [55] used quantum random walks to reduce the sieving exponent from 20.2075n to 20.1327n . Chailloux and Loyer [20] gave a quantum speedup for BKZ’s SVP oracle, achieving block size β in 20.265β quantum gates vs. 20.292β classically. These are quadratic-root speedups and are already incorporated in NIST security levels [4]. For ML-KEM-1024, the reduction is from 2243 to 2220 . The original CDPR attack [9] has been refined. Cramer, Ducas, and Wesolowski [56, 57] √ used Stickelberger relations to improve the approximation factor from exp(Õ( n log n)) to √ √ exp(Õ( n)). Our work reduces it further to exp(O( log n)), a qualitative improvement from super-polynomial to sub-polynomial. p Pellet-Mary, Hanrot, and Stehlé [58] gave a tradeoff: γ = exp(Õ( n · Tpre /Tatt )). In the balanced regime this matches CDW [56,√57]. Our tower PIP makes both preprocessing and attack polynomial, achieving γ = exp(O( log n)) regardless of time allocation. Felderhoff et al. [59] proved that Ideal-SVP remains hard for small-norm prime ideals p with N(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 [60] predicted module-BKZ quality, showing δmodule ≤ 1/d δgeneric for balanced modules. Mureau et al. [61] 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 ≤ 64. Worst-case hardness of SVP and CVP. SVP and CVP are NP-hard to approximate within nc/ log log n for some c > 0 [62, 63]. For constant approximation factors (e.g., γ ≈ 21), NP-hardness of exact SVP does not change, where the approximation regime is believed to be in BQP under GRH [31]. Ideal-SVP hardness. Whether Ideal-SVP is harder than generic SVP is open. Felderhoff et al. [59] showed Ideal-SVP is hard for prime ideals generated by small-norm elements. Our work √ shows principal ideals generated by short elements have γ = O(exp( log n)). Module-LWE worst-case hardness. 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 γCDPR . Quantum hardness of PIP. 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 = Q(ζ2k ), classical PIP costs 2Ω( n log n) . Our tower PIP (Theorem 5.4) achieves O(n3 log2 n) quantum gates, an exponential quantum speedup.
8
Discussion and Open Problems
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 ≈ 254 to ≈ 21, and the PIP complexity from 2Ω(n) to O(n3 log2 n) quantum gates (∼ 108 for ML-KEM-1024).
19
Table 7: Cumulative improvements over the original CDPR attack [9] Component
Original CDPR
Parts I-IV
Class number h+ k Module reduction SGP approx factor σg0 PIP complexity γ (ML-KEM-1024)
Assumed=1 nO(d) blowup √ exp(Õ( n)) √ Θ( n) assumed 2Ω(n) hidden ≈ 254
Proved for k ≤ 12 (Part I) αd = O(1) (Part II) √ exp(O( log n)) (Part III) O(1), q-independent (Part III) O(n3 log2 n) gates (Part IV) ≈ 21 (median); ≤ 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 Acknowledgments will be added in the final version.
References [1] Peter Williston Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26: 1484-1509, 1997. [2] Ronald Linn Rivest, Adi Shamir, and Leonard Max Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21: 120-126, 1978. [3] Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, 22: 644-654, 1976. [4] NIST. Announcing request for nominations for public-key post-quantum cryptographic algorithms. Federal Register, Vol. 81, No. 244, pp. 92787-92788, December 2016. [5] Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Kyber algorithm specifications and supporting documentation (version 3.02). Technical report, NIST PQC Project, Round 3 Submission, 2022. [6] NIST. Module-lattice-based key-encapsulation mechanism standard. Technical Report FIPS PUB 203, U.S. Department of Commerce, August 2024. [7] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes Cryptography, 75:565-599, 2015. [8] Martin R. Albrecht and Amit Deo. Large modulus Ring-LWE ≥ Module-LWE. In ASIACRYPT 2017, volume 10624 of LNCS, pp.267-296. Springer, 2017. [9] Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals in cyclotomic rings. In EUROCRYPT 2016, volume 9666 of LNCS, pp.559-585. Springer, 2016.
20
[10] Lawrence C. Washington. Introduction to Cyclotomic Fields, volume 83 of Graduate Texts in Mathematics. Springer, New York, 2nd edition, 1997. [11] Jürgen Neukirch. Algebraic Number Theory. Springer, 1999. [12] Serge Lang. Algebraic Number Theory, volume 110 of Graduate Texts in Mathematics. Springer, New York, 2nd edition, 1994. [13] Daniele Micciancio. Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2002), pp.356-365. IEEE, 2002. [14] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On ideal lattices and learning with errors over rings. In EUROCRYPT 2010, volume 6110 of LNCS, pp.1-23. Springer, 2010. [15] Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56: 34, 2009. [16] Arjen K. Lenstra, Jr. Hendrik W. Lenstra, and László Lovász. Factoring polynomials with rational coefficients. Mathematische Annalen , 261: 515-534, 1982. [17] Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53: 201-224, 1987. [18] Nicolas Gama and Phong Q. Nguyen. Predicting lattice reduction. In EUROCRYPT 2008, volume 4965 of LNCS, pp.31-51. Springer, 2008. [19] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp.10-24. SIAM, 2016. [20] André Chailloux and Johanna Loyer. Lattice sieving via quantum random walks. In Advances in Cryptology-ASIACRYPT 2021, volume 13093 of LNCS, pp.63-91. Springer, 2021. [21] Warren Sinnott. On the Stickelberger ideal and the circular units of a cyclotomic field. Ann. of Math., 108: 107-134, 1978. [22] László Babai. On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica, 6: 1-13, 1986. [23] Chris Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC 2009), pp.333-342. ACM, 2009. [24] Richard Lindner and Chris Peikert. Better key sizes (and attacks) for LWE-based encryption. In Topics in Cryptology-CT-RSA 2011, volume 6558 of LNCS, pp.319-339. Springer, 2011. [25] David Harvey. Faster arithmetic for number-theoretic transforms. Journal of Symbolic Computation, 60: 113-119, 2014. [26] Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. [27] M. R. Leadbetter, Georg Lindgren, and Holger Rootzén. Extremes and Related Properties of Random Sequences and Processes. Springer, New York, 1983. [28] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. 21
[29] Patrick Billingsley. Convergence of Probability Measures. Wiley, New York, 2nd edition, 1999. [30] Robb J. Muirhead. Aspects of Multivariate Statistical Theory. Wiley, New York, 1982. [31] Jean-François Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving the principal ideal problem. In SODA 2016, pp.893-902. SIAM, 2016. [32] Joachim von zur Gathen and Jürgen Gerhard. Modern Computer Algebra. Cambridge University Press, 3rd edition, 2013. [33] David Harvey and Joris van der Hoeven. Integer multiplication in time O(n log n). Annals of Mathematics, 193: 563-617, 2021. [34] A. Yu. Kitaev. Quantum measurements and the Abelian stabilizer problem. arxiv quantph/9511026, 1995. [35] Christopher M. Dawson and Michael A. Nielsen. The Solovay-Kitaev algorithm. Quantum Information & Computation, 6: 81-95, 2006. [36] Phong Q. Nguyen and Damien Stehlé. An LLL algorithm with quadratic complexity. SIAM Journal on Computing, 39: 874-903, 2009. [37] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland. Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86: 032324, 2012. [38] Eric Dennis, Alexei Kitaev, Andrew Landahl, and John Preskill. Topological quantum memory. Journal of Mathematical Physics, 43: 4452-4505, 2002. [39] Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Prest, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. Falcon: Fast-Fourier lattice-based compact signatures over NTRU. In Submission to the NIST Post-Quantum Cryptography standardization Project (Round 3), 2020. Specification v1.2. [40] Joppe W. Bos, Olivier Bronchain, Léo Ducas, Serge Fehr, Yu-Hsuan Huang, Thomas Pornin, Eamonn W. Postlethwaite, Thomas Prest, Ludo N. Pulles, and Wessel van Woerden. HAWK: Algorithm specifications and supporting documentation, version 1.0.1. Submission to the NIST Post-Quantum Cryptography Additional Digital Signatures Standardization (Round 2), 2024. [41] Andreas Hülsing, Joost Rijneveld, John M. Schanck, and Peter Schwabe. High-speed key encapsulation from NTRU. In Wieland Fischer and Naofumi Homma, editors, Cryptographic Hardware and Embedded Systems-CHES 2017, volume 10529 of LNCS, pp.232-252. Springer, 2017. [42] Cong Chen, Oussama Danba, Jeffrey Hoffstein, Andreas Hülsing, Joost Rijneveld, Tsunekazu Saito, John M. Schanck, Peter Schwabe, William Whyte, Keita Xagawa, Takashi Yamakawa, and Zhenfei Zhang. NTRU: Algorithm specifications and supporting documentation. Submission to the NIST Post-Quantum Cryptography Standardization Project (Round 3), 2020. [43] Clémence Chevignard, Guilhem Mureau, Thomas Espitau, Alice Pellet-Mary, Heorhii Pliatsok, and Alexandre Wallet. A reduction from Hawk to the principal ideal problem in a quaternion algebra. In Advances in Cryptology-EUROCRYPT 2025, volume 15602 of LNCS, pp.154-183. Springer, 2025. 22
[44] NIST. FN-DSA: FFT over NTRU-lattice-based digital signature algorithm (initial public draft). Technical Report FIPS PUB 206 (Draft), U.S. Department of Commerce, 2025. [45] Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp.197-206. ACM, 2008. [46] J. Hoffstein, J. Pipher, and J. H. Silverman. NTRU: A ring-based public key cryptosystem. In Algorithmic Number Theory (ANTS-III), volume 1423 of LNCS, pp.267-288. Springer, 1998. [47] Paul Kirchner and Pierre-Alain Fouque. Revisiting lattice attacks on overstretched NTRU parameters. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, Advances in CryptologyEUROCRYPT 2017, Part I, volume 10210 of LNCS, pp.3-26. Springer, 2017. [48] Yoshinori Aono, Yuntao Wang, Takuya Hayashi, and Tsuyoshi Takagi. Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In Advances in Cryptology-EUROCRYPT 2016, volume 9665 of LNCS, pp.789-819. Springer, 2016. [49] Shi Bai, Damien Stehlé, and Weiqiang Wen. Measuring, simulating and exploiting the head concavity phenomenon in BKZ. In Advances in Cryptology- ASIACRYPT 2018, volume 11272 of LNCS, pp.369-404. Springer, 2018. [50] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2n time using discrete Gaussian sampling. In STOC 2015, pp.733-742. ACM, 2015. [51] Anja Becker, Léo Ducas, Nicolas Gama, and Thijs Laarhoven. New directions in nearest neighbor searching with applications to lattice sieving. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp.10-24. SIAM, 2016. [52] Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12: 415-440, 1987. [53] Martin R. Albrecht, Rachel Player, and Sam Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9: 169-203, 2015. [54] Martin R. Albrecht, Benjamin R. Curtis, Amit Deo, Alex Davidson, Rachel Player, Eamonn W. Postlethwaite, Fernando Virdia, and Thomas Wunderer. Estimate all the LWE, NTRU schemes! Software, https://github.com/malb/lattice-estimator, 2023. [55] Thijs Laarhoven. Sieving for shortest vectors in lattices using angular locality-sensitive hashing. In Advances in Cryptology-CRYPTO 2015, volume 9215 of LNCS, pp.3-22. Springer, 2015. [56] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short Stickelberger class relations and application to Ideal-SVP. In EUROCRYPT 2017, volume 10210 of LNCS, pp.324-348. Springer, 2017. [57] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time. Journal of ACM, 68: 8, 2021. [58] Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehlé. Approx-SVP in ideal lattices with pre-processing. In EUROCRYPT 2019, volume 11477 of LNCS, pp.685-716. Springer, 2019.
23
[59] Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, and Benjamin Wesolowski. Ideal-SVP is hard for small-norm uniform prime ideals. In Theory of Cryptography Conference 2023, volume 14372 of LNCS, pp.324-348. Springer, 2023. [60] Léo Ducas, Lynn Engelberts, and Paola de Perthuis. Predicting module-lattice reduction. In Advances in Cryptology-ASIACRYPT 2025, volume 16247 of LNCS, pp.133-166. Springer, 2025. [61] Guilhem Mureau, Alice Pellet-Mary, Heorhii Pliatsok, and Alexandre Wallet. Cryptanalysis of rank-2 module-LIP in totally real number fields. In EUROCRYPT 2024, volume 14657 of LNCS, pp.238-267. Springer, 2024. [62] Irit Dinur. Mildly exponential reduction from gap-3SAT to polynomial-gap label-cover. Electronic Colloquium on Computational Complexity, TR16-128, 2016. [63] Ishay Haviv and Oded Regev. Tensor-based hardness of the shortest vector problem to within almost polynomial factors. Theory of Computing, 8: 513-531, 2012. [64] Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient public key encryption based on ideal lattices. In Advances in Cryptology-ASIACRYPT 2009, volume 5912 of LNCS, pp.617-635. Springer, 2009. [65] Jean-François Biasse. Subexponential time relations in the class group of large degree number fields. Advances in Mathematics of Communications, 8: 407-425, 2014.
24