arXiv CSopen access

Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice

Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice Ming-Xing Luo School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China

arXiv:2605.17404v1 [cs.DS] 17 May 2026

May 19, 2026

Abstract 2

We prove that the L CVP distance from a random short ring element to the log-unit π √ lattice of Q(ζ2k ) converges to 2√ n as n = 2k−1 → ∞. We then show that this target lies 6 inside the Voronoi cell of the origin for k ≥ 4. For the L∞ norm, the maximum over n sub√ Gaussian coordinates yields O( log n) which translates into a sub-polynomial approximation factor for the Short Generator Problem. We show a Coarse Lattice Theorem that Babai’s algorithm returns zero for all structured targets, yet exactly recovers unit perturbations of arbitrary size. For module determinant ideals, we further prove the Trigamma Theorem that proves an intrinsic imbalance σg0 = O(1) independent of the modulus q. Finally, √ combined with Parts I and II, we reduce the CDPR factor for ML-KEM from exp(Õ( n)) to a sub-polynomial value.

Keywords: Log-unit lattice, Short Generator Problem, CVP, CDPR attack, sub-Gaussian, ML-KEM, post-quantum cryptography.

1

Introduction

The CDPR quantum attack [1] on ideal lattices over R = Z[ζ2k ] achieves an approximation factor √ γ = exp(C0 n log n), where n = 2k−1 , and C0 > 0 is an absolute constant. Refined by Cramer, Ducas, and Wesolowski [2, 3] using Stickelberger relations, this attack implements with three phases. Phase 1 is named as quantum PIP which uses the Biasse-Song algorithm [4] to find some generator g of a given principal ideal I = (g0 ) ⊂ R in quantum polynomial time. Unfortunately, g may be exponentially larger than the shortest generator g0 as g = g0 ϵ for some unit ϵ ∈ R× that can have enormous norm. Phase 2 is log-unit CVP, where Closest Vector Problem (CVP) is resolved on the log-unit lattice Λ to recover ϵ. Note in the log-Minkowski embedding, the generators of ideal I form the coset log|σ(g0 )| + Λ. So, the problem of finding a short generator is then reduced to locate the lattice point closest to log|σ(g)|. In Phase 3, the CVP solution can be used to identify a unit ϵ′ that closes to ϵ. Meanwhile, the short generator is recovered as g ′ = g(ϵ′ )−1 . In this case, the approximation factor is given by γ = exp(ρ∞ ), where ρ∞ denotes the L∞ -norm of the CVP residual. Pellet-Mary, Hanrot, and Stehlé [5] gave a time-approximation tradeoff with preprocessing. Felderhoff et al. [6] proved Ideal-SVP remains hard for small-norm prime ideals. For module lattices, Langlois and Stehlé [7] proved the worst-case MLWE hardness. Mureau et al. [8] and Allombert et al. [9] attacked rank-2 module-LIP. Chevignard et al. [10] reduced Hawk scheme to PIP. Ducas et al. [11] predicted module-BKZ quality. Babai [12] introduced the nearest-plane CVP algorithm, while refs.[13, 14, 15, 16] provide generic lattice reduction with progressively better approximation factors. Note the worst-case bound treats the CVP target as an arbitrary point in the ambient space. However, the targets arising from short generators are highly structured: they are log-embeddings 1

of ring elements with small coefficients. A natural question is whether this structure can be exploited to obtain tighter bounds. Our goal in what follow is to answer this problem. Our probabilistic methods use classical central limit theorem (CLT) (Lindeberg [17, 18]) and sub-Gaussian concentration inequalities from Vershynin [19] and Boucheron-Lugosi-Massart [20], the QR decomposition of random matrices and the associated χ-squared distributions from Tao [21], and the trigamma functions from Abramowitz-Stegun [22]. Specifically, we prove the following results. • Theorem 4.1 For a short element g ∈ R with i.i.d. bounded coefficients, its L2 distance √ π √ n ≈ 0.6413 n. from ΠH0 (log|σ(g)|) to Λ converges to 2√ 6 • Theorem 4.2 The structured target vector lies inside the Voronoi cell of the origin in Λ with probability 1 − o(1) for k ≥ 4. √ • Theorem 4.3 The L∞ distance√is O( log n) for short generators, which implies the approximation factor γ = exp(O( log n)) = o(nϵ ) for every ϵ > 0. For ML-KEM scheme (n = 256), γ ≈ 24.1 (Gaussian) or 24.9 (ring), far below the threshold. The rest of this paper is organized as follows. Section 2 introduces some preliminaries of the log-unit lattice, Babai’s nearest-plane algorithm, and complex Gaussians. Section 3 contributes the embedding uncorrelatedness, central limit theorem, and variance identity. Section 4 presents three CVP distance Theorems. Section 5 shows the Coarse Lattice Theorem. Section 6 provides the Trigamma Theorem and its implications for ML-KEM security while Section ?? concludes the paper.

2

Preliminaries

This section introduces algebraic, geometric, and probabilistic foundations used in the following sections.

2.1

Setup and notation

2πi/m The cyclotomic field K = Q(ζ) is obtained by adding a primitive m-th Pn−1root iof unity ζ = e to the rational number field. Elements of K are represented by i=0 ai ζ with ai ∈ Q. The degree of K is [K : Q] = n = φ(m) = 2k−1 , because ζ satisfies the minimal polynomial xn + 1 over Q which is valid for m = 2k with k ≥ 3. The ring of integers R = Z[ζ] consists of elements with integer coefficients ai ∈ Z. The Galois group Gal(K/Q) consists of all field automorphisms of K that fix the field Q. Since every such automorphism will map ζ to another primitive m-th root of unity, Gal(K/Q) can be identified with (Z/mZ)× , i.e., the group of integers modulo m coprime to m. For m = 2k , these are the odd integers a ∈ {1, 3, 5, . . . , m − 1}, and the corresponding automorphism σa is defined by σa (ζ) = ζ a . This action is well-defined and can be extended to all of K by linearity. An embedding σj : K ,→ C is a ring homomorphism from K into the complex numbers. Since K is complex for k ≥ 3, all n embeddings are mapped into C \ R. The conjugate pair of embeddings satisfies σm−j = σj (g) for all g ∈ K, because ζ m−j = ζ j . P(g) n−1 For an element g = i=0 ci ζ i ∈ R, the j-th embedding can be defined by evaluating the polynomial at ζ j , i.e.,

σj (g) =

n−1 X

ci ζ ij =

i=0

n−1 X

ci e2πi·ij/m .

(1)

i=0

This is a discrete Fourier transform (DFT) of the vector (c0 , . . . , cn−1 ) evaluated at the n-th roots of −1 from ζ n = eπi = −1. 2

Definition 2.1. The log-embedding of g ∈ R \ {0} is the vector of coordinate-wise log-moduli defined by
L(g) = log|σj (g)| odd j ∈ Rn . (2) This mapping transforms the multiplicative of R into additive in Rn as L(g1 g2 ) = L(g1 ) + L(g2 ),

(3)

because |σj (g1 g2 )| = |σj (g1 )| · |σj (g2 )|. Especially, g = g0 ϵ becomes L(g) = L(g0 ) + L(ϵ) for g0 ∈ R \ {0} and ϵ ∈ R× . P The trace-zero hyperplane is defined by H0 = {x ∈ Rn : j xj = 0}. The orthogonal projection onto H0 is then defined by ΠH0 (L(g)) = L(g) −

1 log|NK/Q (g)| · 1, n

(4)

Q where the field norm NK/Q (g) = odd j σj (g), i,e., the product over all n embeddings indexed by j ∈ {1, 3, . . . , m − 1}. Here, conjugate pairs σj and σm−j satisfy σm−j (g) = σj (g). Denote J = {1, 3, . . . , n − 1} as a set representative for all n2 conjugate pairs. Then σj (g) · σm−j (g) = |σj (g)|2 for each j ∈ J. So, NK/Q (g) is real and positive as Y Y NK/Q (g) = |σj (g)|2 = |σj (g)|. (5) j∈J

odd j

The field norm is a rational integer for g ∈ R. P The log-unit lattice Λ lies in H0 since units ϵ satisfy |N(ϵ)| = 1 and j log |σj (ϵ)| = log|N(ϵ)| = 0. So, CVP will be defined in H0 . Moreover, using the projection (4), the CVP distance is independent of the overall scale of g.

2.2

The log-unit lattice

By Dirichlet’s Unit Theorem [23], the unit group of a number field K with r1 real and r2 pairs of complex embeddings has unit rank r1 + r2 − 1. For K = Q(ζ2k ) with k ≥ 3, we have r1 = 0 and r2 = n2 . This gives unit rank r = n2 − 1. The log-embedding L(ϵ) for a unit ϵ satisfies log |σj (ϵ)| = log |σm−j (ϵ)| by conjugation, so we have effective dimension n2 and the lattice rank in H0 r = n2 − 1. sin(aπ/m) Since h+ k = 1 for k ≤ 12 (Part I), the cyclotomic units ξa = sin(π/m) for odd a ∈ {3, 5, . . . , n− 1} generate R× modulo torsion [24, 25]. Definition 2.2. The log-unit lattice is defined by Λ = {(log |σj (ϵ)|)odd j : ϵ ∈ R× } ⊂ H0 .

(6)

Its rank r = n2 −1 and a basis {ba } is indexed by a ∈ {3, . . . , n−1}, where ba = ΠH0 ((log |σj (ξa )|)j ). Λ is an ( n2 − 1)-dimensional lattice in the (n − 1)-dimensional hyperplane H0 ⊂ Rn . Its points correspond to the logarithmic signatures of units. The CVP on Λ asks: given the log-signature of an arbitrary generator, find the unit whose log-signature is closest. Definition 2.3. The Lp -cover radius of a lattice Λ ⊂ Rm is defined by µp (Λ) = max min∥t − v∥p . t∈Rm /Λ v∈Λ

(7)

This radius is the maximum √ CVP distance over all possible target vectors. The CDPR method [1] uses µ∞ (Λ) = O( n log n). Instead, we show structured targets are much closer than this worst case. 3

Definition 2.4. The Voronoi cell of a lattice point v ∈ Λ is defined as V(v) = {t ∈ Rm : ∥t − v∥2 ≤ ∥t − w∥2 for all w ∈ Λ}.

(8)

A point t lies in V(0) if and only if 2⟨t, w⟩ ≤ ∥w∥22 for every nonzero w ∈ Λ (the Voronoi condition).

2.3

Babai’s nearest-plane algorithm

Babai’s algorithm [12] is the standard polynomial-time CVP approximation used in Phase 2 of the CDPR attack [1]. Definition 2.5. Given a basis B = (b1 , . . . , br ) of a lattice Λ ⊂ Rm , the Gram-Schmidt orthogonalization (GSO) produces orthogonal vectors b′1 , . . . , b′r as b′i = bi −

X

µij b′j ,

j<i

µij =

⟨bi , b′j ⟩ ∥b′j ∥22

.

(9)

√ For the log-unit lattice, these norms are Ω( n) (Table 1) which is large relative to O(1) per-component deviation of structured targets. The basis matrix B ∈ Rm×r admits a QR decomposition B = QR, where Q ∈ Rm×r has orthonormal columns and R ∈ Rr×r is an upper triangular with positive diagonal. The two factorizations are related by Qi =

b′i , ∥b′i ∥2

Rii = ∥b′i ∥2 ,

Rji = µij ∥b′j ∥2

(j < i).

(10)

Definition 2.6 (Babai’s nearest-plane algorithm [12]). Given a lattice basis B = (b1 , . . . , br ) with GSO (b′1 , . . . , b′r ) and a target t ∈ Rm , Babai’s algorithm computes integer coefficients cr , cr−1 , . . . , c1 as j ⟨t − P cj bj , b′ ⟩ m i j>i , i = r, r − 1, . . . , 1, (11) ci = ∥b′i ∥22 where P ⌊·⌉ denotes rounding to the nearest integer. The output lattice vector is given by v = ri=1 ci bi with Babai residual e = t − v. P The Babai residual satisfies e = ri=1 (µi − ci )b′i + t⊥ , where t⊥ is the component of t which is orthogonal to span(b1 , . . . , br ), and µi is the projection coefficient computed at step i. Moreover, the Babai residual satisfies √ r max ∥b′ ∥2 + ∥t⊥ ∥2 . (12) ∥t − v∥2 ≤ 2 1≤i≤r i When Λ has full column rank of m = r, t⊥ vanishes and the bound simplifies into √ r ∥t − v∥2 ≤ max ∥b′ ∥2 . (13) 2 1≤i≤r i √ For the log-unit lattice Λ with rank r = n2 − 1 and GS norms ∥b′i ∥2 = Ω( n), the Babai bound gives ∥e∥2 = O(n). This is the worst case guarantee over all targets. For structured targets, we will show the projection coefficients µi are not bounded by 12 . Babai’s algorithm costs O(r2 ) arithmetic operations on GS coefficients (or O(r2 m) if the vectors are in Rm ). For the log-unit lattice with r = n2 − 1 and m = n, the total cost is O(n3 ) which might be negligible compared to the PIP step. 4

2.4

Probabilistic definitions

We collect some probabilistic definitions used in the following proofs. Definition 2.7. A circularly symmetric complex Gaussian Z ∼ CN (0, σ 2 ) is Z = X + iY , where X, Y ∼ N (0, σ 2 /2) are independent. Circular symmetry means Z and eiθ Z have the same distribution for every θ. The squared modulus satisfies |Z|2√ /σ 2 ∼ Exp(1) (exponential with rate 1), P and |Z| has Rayleigh distribution with parameter σ/ 2. The circular symmetry of each σj (g) = ci e2πi·ij/m is from the fact that the summands are i.i.d. terms rotated by different angles, uniformly distributed modulo 2π. Definition 2.8. [19] A centered real random variable X is sub-Gaussian with parameter σ 2 , denoted as X ∼ subG(0, σ 2 ), if the following condition holds 2 2

E[etX ] ≤ eσ t /2

for all t ∈ R.

(14)

Note the sum of independent sub-Gaussian variables is sub-Gaussian, and any bounded variable with |X| ≤ B is sub-Gaussian with parameter B 2 from the Hoeffding’s Lemma [26]. P i.i.d. Definition 2.9. If W1 , . . . , Wk ∼ N (0, 1), then ki=1 Wi2 is the χ-squared distribution (χ2k ) with k degrees of freedom. It satisfies E[χ2k ] = k and Var(χ2k ) = 2k. The logarithmic moments, which are central to our Trigamma Theorem, involve the digamma and trigamma functions as

E[log χ2k ] = ψ k2 + log 2, Var(log χ2k ) = ψ ′ k2 . (15) d Definition 2.10. [22] The digamma function is defined by ψ(z) = dz log Γ(z) and trigamma 2 d ′ function is ψ (z) = dz 2 log Γ(z).

NoteP ψ(1) = −γ, where γ ≈ 0.5772 is the Euler-Mascheroni constant. Moreover, we have −2 ψ ′ (z) = ∞ k=0 (z + k) , which is positive, strictly decreasing, and tends to 1/z for large z. For z = 1, we have ψ ′ (1) = π 2 /6. Notation 2.1. We fix the following notation throughout this part: • k ≥ 3 is an integer, n = 2k−1 , m = 2k = 2n, ζ = e2πi/m . • R = Z[ζ] is the ring of integers of K = Q(ζ). • The Galois group Gal(K/Q) ∼ = (Z/mZ)× acts via σa : ζ 7→ ζ a for odd a. • The n complex embeddings are σj for odd j ∈ {1, 3, . . . , m − 1}. • Conjugate pairs: σm−j (g) = σj (g). • J =P {1, 3, . . . , n − 1} indexes one representative from each conjugate pair; |J| = n/2. i • g = n−1 i=0 ci ζ with ci drawn i.i.d. from a real-valued distribution with mean 0, variance 2 σc > 0, and finite fourth moment. n • L(g) = (log |σj (g)|) Podd j ∈ R is the log-embedding. n • H0 = {x ∈ R : j xj = 0} is the trace-zero hyperplane. ΠH0 is orthogonal projection onto H0 . • Λ = {L(ϵ) : ϵ ∈ R× } ⊂ H0 is the log-unit lattice with rank r = n/2 − 1. • Õ(f ) means O(f · polylog(f )).

3

The CLT for Embeddings and Variance Identity

In this section, we prove two results for ring-based lattice cryptanalysis: (1) different canonical embeddings of a random ring element are pairwise uncorrelated and asymptotically jointly independent in the large-dimension limit; (2) for a circularly symmetric complex Gaussian random variable Z ∼ CN (0, 1), the variance of log |Z| is π 2 /24. 5

3.1

Embedding uncorrelatedness

P i 2 Lemma 3.1. Let g = n−1 i=0 ci ζ with ci i.i.d. real-valued, mean 0, variance σc < ∞. Then for different odd j, j ′ ∈ {1, 3, . . . , 2n − 1} we have E[σj (g)σj ′ (g)] = 0.

(16)

P ij Proof. By definition, we have σj (g) = n−1 m-th root of unity ζ = e2πi/m i=0 ci ζ Pfor the primitive P n−1 −i′ j ′ . We then obtain i′ j ′ = with m = 2n. For real ci′ ∈ R, we get σj ′ (g) = n−1 i′ =0 ci′ ζ i′ =0 ci′ ζ n−1 h n−1 i X X ′ ′ E[σj (g)σj ′ (g)] = E ( ci ζ ij )( ci′ ζ −i j )

=

i=0 n−1 X n−1 X

i′ =0 ′ ′

E[ci ci′ ]ζ ij−i j ,

(17)

i=0 i′ =0

where the second equality is from the linearity of expectation. From the i.i.d. zero-mean of ci s, we obtain E[ci ci′ ] = 0 for all i = ̸ i′ , and E[c2i ] = σc2 for all 0 ≤ i ≤ n − 1. Using this orthogonality for Eq.(17), we get E[σj (g)σ

j′

(g)] = σc2

n−1 X

′

ζ i(j−j ) .

(18)

i=0

Let c = j − j ′ . Since j and j ′ are different odd integers, c isPa non-zero even integer with 1−ζ nc ic 0 < |c| < 2n = m. We compute Eq.(18) using the equality of n−1 i=0 ζ = 1−ζ c . This holds because ζ c ̸= 1, where ζ is a primitive m-th root of unity and ζ k = 1 if and only if m divides k. Using the definition of ζ, we have ζ n = e2πi·n/m = eπi = −1. Note c is even, (ζ n )c = (−1)c = 1. Thus, from Eq.(18), we obtain the equality (16).

3.2

Central Limit Theorem

Proposition 3.1. Under the conditions of Lemma 3.1, suppose that ci has a finite fourth moment. Then for any fixed different odd indices j1 , . . . , js , the following result holds  σ (g) σj (g)  d j p1 , . . . , ps − → (Z1 , . . . , Zs ), nσc2 nσc2

i.i.d.

Zℓ ∼ CN (0, 1).

(19)

Proof. For each p embedding index ℓ ∈ {1, . . . , s} and coefficient index i ∈ {0, 1, . . . , n − 1}, define Yi,ℓ = ci ζ ijℓ / nσc2 , where ζ = e2πi/m with m = 2n. We decompose the normalized embedding as n−1 n−1 σj (g) 1 X ijℓ X pℓ =p ci ζ = Yi,ℓ . nσc2 nσc2 i=0 i=0

(20)

For each i, define the s-dimensional complex random vector as ci Yi = (Yi,1 , Yi,2 , . . . , Yi,s ) = p (ζ ij1 , ζ ij2 , . . . , ζ ijs ). 2 nσc

(21)

The factors ζ ijℓ (ℓ = 1, . . . , s) are deterministic complex numbers of modulus 1. So, Yi p is a deterministic vector in Cs which is scaled by the random scalar ci / nσc2 . All vectors Y0 , . . . , Yn−1 are mutually independent.

6

  Since E[ci ] = 0 implies E[Yi ] = 0, for the complex covariance Cov(U, V ) = E U V with centered random variables U and V , we get Cov

n−1 X

Yi,ℓ ,

n−1 X

i=0

 n−1 X Yi,ℓ′ = E[Yi,ℓ Yi,ℓ′ ].

i=0

(22)

i=0

From Eq.(22), we obtain "

ci ζ ijℓ ci ζ −ijℓ′ E[Yi,ℓ Yi,ℓ′ ] = E p · p nσc2 nσc2

# =

E[c2i ] i(jℓ −jℓ′ ) 1 ·ζ = · ζ i(jℓ −jℓ′ ) , 2 nσc n

(23)

where we have used the equality ζ ijℓ′ = ζ −ijℓ′ and E[c2i ] = σc2 . We then obtain n−1 X

n−1

E[Yi,ℓ Yi,ℓ′ ] =

1 X i(jℓ −jℓ′ ) ζ . n

(24)

i=0

i=0

In what follows, we evaluate the sum (24) in two cases. For ℓP = ℓ′ , we have jℓ − jℓ′ = 0, 1 i(j −j ) 0 ′ ′ ℓ ℓ so ζ = ζ = 1 for all is. Moreover, from Eq.(24), we get n n−1 i=0 1 = 1; For ℓ ̸= ℓ , let c = jℓ − jℓ′ . c is a non-zero even integer. Similar to the proof of Lemma 3.1, we have n−1 X

ζ ic =

i=0

1 − ζ nc 1 − (−1)c = = 0, 1 − ζc 1 − ζc

(25)

where the second equality is from ζ n = −1, while the third equalityPholds as c is even. Combining with two cases, we obtain the covariance matrix of n−1 i=0 Yi as Σn = (Σn )ℓ,ℓ′ = δℓ,ℓ′ · Is ,

(26)

where δℓ,ℓ′ is the Kronecker delta, and Is is rank s identity matrix. For the 2s-dimensional real CLT, the Lindeberg condition [17] requires for every fixed ε > 0, Ln (ε) :=

n−1 X

E[∥Yi ∥22 · 1{∥Yi ∥2 >ε} ] → 0 as n → ∞,

(27)

i=0

P where ∥Yi ∥22 = sℓ=1 |Yi,ℓ |2 , and 1{·} is the indicator function. Using Eq.(21), we firstly simplify the norm as ∥Yi ∥22 =

s X

|Yi,ℓ |2 =

ℓ=1

s X c2 i

ℓ=1

· |ζ ijℓ |2 = 2

nσc

sc2i , nσc2

(28)

where the final equality is from |ζ ijℓ | = 1 for all i, ℓ. From Eq.(27), we then get n−1 X

h sc2 i i √ 2 E · 1 nσc2 {|ci |>ε nσc /s} i=0 h i s = 2 · E c20 · 1{|c |>ε√nσ2 /s} . 0 c σc

Ln (ε) =

(29)

We now prove Ln (ε) → 0 when n → ∞. Define fn (ω) = c0 (ω)2 · 1{|c (ω)|>ε√nσ2 /s} . We can 0 c show the convergence via the Lebesgue Dominated Convergence Theorem, using the following facts: • For every outcome ω with finite c0 (ω) (which holds almost surely, as c0 has a finite fourth p moment), ε nσc2 /s → ∞ when n → ∞. 7

• For all n, we have |fn (ω)| ≤ c0 (ω)2 almost surely. So, we obtain E[fn ] → 0 when n → ∞. Since s and σc2 are fixed constants independent of n, we have Ln (ε) = σs2 E[fn ] → 0. c We now use Cramér–Wold Theorem [27, 28]. In our setting, we identify Cs with R2s via the mapping Zℓ 7→ (ℜ(Zℓ ), ℑ(Zℓ )) for Psℓ = 1, . . . , s. For any fixed real vector Pn−1a = 2s (a1 , b1 , a2 , b2 , . . . , as , bs ) ∈ R , define Tn := ℓ=1 (aℓ ℜ(Sn,ℓ )+bℓ ℑ(Sn,ℓ )), where Sn,ℓ = i=0 Yi,ℓ is the ℓ-th component. Decompose Tn into a sum of n independent real random variables as Tn =

n−1 X i=0

Wi ,

Wi =

s X

(aℓ ℜ(Yi,ℓ ) + bℓ ℑ(Yi,ℓ )).

(30)

ℓ=1

By the Cauchy–Schwarz inequality, we obtain n−1 X

E[Wi2 · 1{|Wi |>ε} ] ≤ ∥a∥22 · Ln (ε/∥a∥2 ) → 0

as n → ∞.

(31)

i=0

This means the one-dimensional Lindeberg condition holds for every linear combination Tn . (2s) We next compute the variance of Tn . Using Σn = 21 I2s , we obtain 1 2 Var(Tn ) = aT Σ(2s) n a = ∥a∥2 . 2 From the one-dimensional Lindeberg CLT [29], we get   1 d Tn − → N 0, ∥a∥22 2

(32)

(33)

when n → ∞. Now, let Z = (Z1 , . . . , Zs ) be a random vector with i.i.d. components Zℓ ∼ CN (0, 1). For P the same linear combination a, T = sℓ=1 (aℓ ℜ(Zℓ ) + bℓ ℑ(Zℓ )) has the distribution N (0, 12 ∥a∥22 ). d

Thus, Tn − → T for every fixed a ∈ R2s . Using the Cramér–Wold Theorem [27, 28], we get the joint convergence in distribution (19). This implies each component ℜ(Zℓ ) and ℑ(Zℓ ) are marginally distributed as N (0, 12 ). All 2s real components are pair-wise uncorrelated. For jointly Gaussian random variables, this implies the uncorrelatedness is equivalent to independence. Therefore, for each ℓ, we have ℜ(Zℓ ) and ℑ(Zℓ ) are independent, so Zℓ = ℜ(Zℓ ) + iℑ(Zℓ ) ∼ CN (0, 1). Moreover, for different ℓ ̸= ℓ′ , Zℓ and Zℓ′ are independent. Thus, the limiting random variables Z1 , Z2 , . . . , Zs are i.i.d. CN (0, 1). This completes the proof. For the parameter set n = 256 (ML-KEM standard), using Berry–Esséen Theorem [30, 31] √ gives a uniform CDF approximation error of O(E[|c0 |3 ]/(σc3 n)), which evaluates to approximately p0.038 for typical coefficient distributions. This means the Gaussian approximation σj (g)/ nσc2 ≈ Zj is accurate to within roughly 4% in CDF. This is sufficient for the variance and maximum norm computations in Theorems 4.1 and 4.3.

3.3

The variance identity

The second result is the exact computation of Var(log |Z|) for a circularly symmetric complex Gaussian random variable Z ∼ CN (0, σ 2 ). Lemma 3.2. Let Z ∼ CN (0, σ 2 ). Then for every σ 2 > 0 we have (i) E[log |Z|] = 12 log σ 2 − γ2 , where γ ≈ 0.5772 is the Euler–Mascheroni constant. 2

(ii) Var(log |Z|) = π24 ≈ 0.4112. 8

Proof. For Z = X + iY ∼ CN (0, σ 2 ), X and Y are independent and identically distributed as N (0, σ 2 /2). Thus, |Z|2 = X 2 + Y 2 has a scaled χ-squared distribution with 2 degrees of freedom. 2 Define W := |Z| . Note X 2 /(σ 2 /2) ∼ χ21 and Y 2 /(σ 2 /2) ∼ χ21 are independent, so σ2 2 2 2 |Z| /(σ /2) ∼ χ2 . The χ22 distribution has density 21 e−t/2 1{t>0} . We then express log |Z| in terms of W as log |Z| =

1 1 1 1 log |Z|2 = (σ 2 W ) = log σ 2 + log W. 2 2 2 2

(34)

The term 21 log σ 2 is a deterministic constant. Thus, we obtain 1 1 log σ 2 + E[log W ], 2 2 1  1 Var(log |Z|) = Var log W = Var(log W ). 2 4 E[log |Z|] =

(35) (36)

For W ∼ Exp(1) and any real s > −1, we have Z ∞ s E[W ] = ws e−w dw = Γ(s + 1).

(37)

0

For s > −1, we have d d E[W s ] = ds ds

Z ∞

ws e−w dw = E[W s log W ].

(38)

0

For s = 0, we obtain d Γ(s + 1) s=0 = Γ′ (1). ds

(39)

d2 d2 s E[W ] = Γ(s + 1) s=0 = Γ′′ (1). s=0 ds2 ds2

(40)

E[log W ] = Differentiating with second time, we get E[(log W )2 ] =

The digamma function ψ(s) is given as ψ(s) = At s = 1, we have Γ(1) =

d Γ′ (s) log Γ(s) = . ds Γ(s)

(41)

R ∞ −w dw = 1. So, 0 e Γ′ (1) = Γ(1) · ψ(1) = ψ(1).

(42)

From the Weierstrass product representation of Gamma functions [32, 33], combining with Eqs.(42) and (40), we get E[log W ] = −γ. From Eq.(35), we obtain E[log |Z|] =

1 1 1 γ log σ 2 + (−γ) = log σ 2 − . 2 2 2 2

(43)

This proves part (i). To compute the second moment E[(log W )2 ] = Γ′′ (1), we use the product rule. In fact, we have Var(log W ) = E[(log W )2 ] − (E[log W ])2 = Γ′′ (1) − (Γ′ (1))2 =

π2 . 6

(44)

From Eq.(36), we get Var(log |Z|) =

1 Var(log W ) ≈ 0.4112. 4

This completes the proof of part (ii). 9

(45)

4

The CVP Distance Theorems

In this section, we prove three results for the structured closest vector problem (CVP) over the log-unit lattice.

4.1

The exact L2 distance constant

This subsection proves the precise asymptotic L2 distance. P i Theorem 4.1. Let g = ci ζ ∈ R with ci i.i.d., mean 0, variance σc2 > 0, and finite fourth moment. Conditioned on g ̸= 0, we have 2 1 p π − ∥ΠH0 (L(g))∥22 → n 24

(46)

p

p

π when n → ∞. Equivalently, √1n ∥ΠH0 (L(g))∥2 → − 2√ ≈ 0.6413, where → − denotes convergence in 6 probability.

Proof. The proof proceeds in seven steps. Step 1.PFor each odd index j ∈ {1, 3, . . . , m − 1}, define the log-modulus tj = log |σj (g)|, and let t̄ = n1 j odd tj denote the average of these log-moduli. Using the definition of hyperplane H0 , we obtain ΠH0 (L(g)) = (tj − t̄)j odd ∈ H0 .

(47)

From this representation, we get ∥ΠH0 (L(g))∥22 =

X

(tj − t̄)2 .

(48)

j odd

Step 2. For 2-power cyclotomic fields, the canonical embedding satisfies the relation σm−j (g) = σj (g). Taking moduli on both sides gives |σm−j (g)| = |σj (g)|, and hence tm−j = tj from the definition of tj . This implies the n coordinates of L(g) form n/2 identical pairs. So, for each pair (j, m − j) its contribution to Eq.(48) is (tj − t̄)2 + (tm−j − t̄)2 = 2(tj − t̄)2 . Let J = {1, 3, . . . , n − 1} with |J| = n/2. From Eq.(48), we obtain X X X (tj − t̄)2 = [(tj − t̄)2 + (tm−j − t̄)2 ] = 2 (tj − t̄)2 . j∈J

j odd

(49)

(50)

j∈J

Using the same conjugate symmetry, we rewrite t̄ as t̄ =

1 X 1X 2X tj = (tj + tm−j ) = tj . n n n j odd

j∈J

(51)

j∈J

p Step 3. By Proposition 3.1, σj (g)/ nσc2 converges in distribution to Zj ∼ CN (0, 1). Applying the continuous mapping theorem to the function log | · | : C \ {0} → R, we obtain log |σj (g)| = log

p σj (g) d 1 nσc2 · p − → log(nσc2 ) + log |Zj |. 2 2 nσc

(52)

From Lemma 3.2(i), we have E[log |Zj |] = −γ/2. Define the centered random variable as Xj := tj −

1 γ log(nσc2 ) + 2 2 10

(53)

d

→ log |Zj | + γ/2. We compute so that Xj − E[log |Zj | +

γ ] = 0, 2

Var(log |Zj | +

γ π2 ) = Var(log |Zj |) = , 2 24

(54)

where the second equality is from Lemma 3.2(ii). Step 4. From the definition (53), we get tj = Xj + 12 log(nσc2 ) − γ2 . Combining with Eq.(51) implies t̄ =

2X 2X 1 γ tj = (Xj + log(nσc2 ) − ) n n 2 2 j∈J

j∈J

1 γ = log(nσc2 ) − + X̄, 2 2 P where we have used the sample mean X̄ := n2 j∈J Xj and n2 is from the definition of t̄. From Eq.(50), we rewrite the squared projected norm as X (Xj − X̄)2 . ∥ΠH0 (L(g))∥22 = 2

(55)

(56)

j∈J

To decompose this sum, we use the standard algebraic identity for sample variance as N X

(Xj − X̄)2 =

j=1

X

Xj2 − N X̄ 2 .

(57)

n · X̄ 2 . 2

(58)

j=1

1 P

Using N = |J| = n/2 and X̄ = N

N X

j∈J Xj , we get

(Xj − X̄)2 =

j∈J

X j∈J

Xj2 −

Dividing both sides of Eq.(56) by n and using Eq.(58), we obtain 2X 2X 2 1 ∥ΠH0 (L(g))∥22 = (Xj − X̄)2 = Xj − X̄ 2 . n n n j∈J

(59)

j∈J

Step 5. By Proposition 3.1, for any fixed finite collection of different indices j1 , . . . , js , the random vector (Xj1 , . . . , Xjs ) converges jointly in distribution to a vector of i.i.d. copies of log |Z| + γ/2. The vector (Xj21 , . . . , Xj2s ) then converges jointly in distribution to i.i.d. copies of (log |Z| + γ/2)2 . We now compute expectation using the eqaulity E[Y 2 ] = Var(Y ) + (E[Y ])2 as h  γ i γ 2 π 2 γ E (log |Z| + )2 = Var(log |Z| + ) + E[log |Z| + ] = , 2 2 2 24

(60)

where the second equality is from the fact log |Z| + γ/2 has mean zero and variance π 2 /24 from Step 3 and Lemma 3.2. Note Xj = tj − 12 log(nσc2 ) + γ/2 with tj = log |σj (g)|. Combining the finite fourth moment p of ci with the Marcinkiewicz–Zygmund Inequality [34, 35], we obtain that E[|σj (g)/ nσc2 |−4 ] is uniformly bounded over n, which further implies supn E[Xj4 ] < ∞. For uniformly integrable triangular arrays [26], we then obtain Sn =

1 X 2 p h γ i π2 Xj → − E (log |Z| + )2 = . n/2 2 24 j∈J

11

(61)

d

Step 6. For each Xj , we have E[Xj ] → 0 when n → ∞, since Xj − → log |Z| + γ/2 and the limiting random variable has mean zero. From the linearity of expectation, we get E[X̄] = 2 P E[X ] → 0. j j∈J n Moreover, we have X 2X 4 Var(X̄) = Var( Xj ) = 2 · Var( Xj ). (62) n n j∈J

j∈J

Decomposing this variance into diagonal and off-diagonal terms as X X X Var( Xj ) = Var(Xj ) + Cov(Xj , Xk ). j∈J

j∈J

(63)

j,k∈J,j̸=k

From the CLT and Lemma 3.2, we get Var(Xj ) → π 2 /24 as n → ∞. Summing over n/2 terms in J gives X

Var(Xj ) =

j∈J

n π2 nπ 2 · ( + o(1)) = + o(n). 2 24 48

(64)

From Lemma 3.1, the embeddings σj (g) and σk (g) are uncorrelated for different j and k. From Proposition 3.1, for independent random variables, its covariance is zero. This implies Cov(Xj , Xk ) = o(1) when n → ∞ for each fixed pair j ̸= k. Note Cov(Xj , Xk ) depends only on j − k modulo m by the stationarity of the discrete Fourier transform. We get  n2 1  X · = O(n). (65) | Cov(Xj , Xk )| = O 4 n j,k∈J,j̸=k

Using Proposition 3.1, the total off-diagonal contribution is o(n). So, from Eqs.(64), (65), and (63), we obtain Var(X̄) =

4 nπ 2 π2 · ( + o(n)) = + o(1/n) → 0 n2 48 12n

(66)

when as n → ∞. Using the Chebyshev’s Inequality [26], for any fixed δ > 0, we have Pr[|X̄| > δ] ≤

Var(X̄) + (E[X̄])2 . δ2

(67) p

Since E[X̄] → 0 and Var(X̄) → 0, the right-hand side tends to zero as n → ∞. Hence, X̄ → − 0. For the function f (x) = x2 , we obtain p

X̄ 2 → − 0.

(68)

Step 7. Combining Steps 5 and 6, using the Slutsky’s Theorem [17], we obtain 2 1 p π ∥ΠH0 (L(g))∥22 → − . n 24

(69)

This further implies 1 p √ ∥ΠH0 (L(g))∥2 → − n

r

π2 ≈ 0.6413. 24

(70)

Finally, note the event of g = 0 requires all ci s vanish simultaneously, so Pr[g = 0] = Pr[c0 = 0]n . For any distribution with σc2 > 0, we have Pr[c0 = 0] < 1. Hence, Pr[g = 0] ≤ pn0 for some p0 < 1. Conditional on g ̸= 0, it changes probabilities by at most Pr[g = 0] = o(1). This completes the proof. 12

4.2

Voronoi cell containment

Theorem 4.1 computes the L2 distance from the structured target vector to the origin of the log-unit lattice. This subsection proves that with overwhelming probability the origin is indeed the nearest lattice point to t. Theorem 4.2. Let k ≥ 4, and g ∈ R be a non-zero ring element with i.i.d. coefficients ci ∈ {−B, . . . , B} for some fixed B ≥ 1. Let t = ΠH0 (L(g)) ∈ H0 , and Λ denote the rank-( n2 − 1) log-unit lattice. Then the following results hold: (i) Gaussian model. If each non-conjugate  embedding is an  i.i.d. CN (0, 1) random variable, n then t ∈ V(0) with probability 1 − exp − 2 log n + O(n) . (ii) Real ring model. The output vector t ∈ V(0) holds with a probability 1 − o(1), suppose there exists a constant c0 > 0 (depending only on B) such that for every non-zero v ∈ Λ and every λ with |λ| ≤ c0 /∥v∥∞ , log E[eλ⟨t,v⟩ ] =

π2 2 λ ∥v∥22 + O(λ3 ∥v∥∞ ∥v∥22 ) + o(∥v∥22 ). 24

Consequently, under either model, the exact CVP distance satisfies √ π √ d(t, Λ) = ∥t∥2 = √ n + o( n). 2 6

(71)

(72)

Note the Voronoi cell V(0) ⊂ H0 contains all points in H0 that are closer to the origin than to any other lattice point in Λ. By the Euclidean lattice Voronoi characterization, t ∈ V(0) if and only if 2⟨t, v⟩ ≤ ∥v∥22

(73)

for every non-zero v ∈ Λ. For each non-zero v ∈ Λ, we define the bad event Ev = {2|⟨t, v⟩| ≥ ∥v∥22 }. 4.2.1

Proof of Part (i)

P For any v ∈ Λ ⊂ H0 , we have j odd vj = 0 (by definition of H0 ) and conjugate symmetry vj = vm−j , and tj = tm−j . This implies that X X X ⟨t, v⟩ = (tj − t̄)vj = t j vj = 2 tj vj , (74) j odd

j odd

j∈J

where J = {1, 3, . . . , n − 1}. Under the Gaussian model, non-conjugate embeddings are i.i.d. Zj ∼ CN (0, 1). So tj = log |Zj | = 12 log Wj with Wj = |Zj |2 ∼ Exp(1). From Eq.(74) we have X vj log Wj . (75) ⟨t, v⟩ = j∈J

By independence of Wj s, the moment generating function (MGF) of ⟨t, v⟩ is give by Y MG (λ) := E[eλ⟨t,v⟩ ] = Γ(1 + λvj ).

(76)

j∈J

For |λ| ≤ 1/(2∥v∥∞ ), we have |λvj | ≤ 1/2 for all j. Using the Taylor expansion log Γ(1 + s) = 2 −γs + π12 s2 + O(|s|3 ) for |s| ≤ 1/2, we get   2 X X X π log MG (λ) = −γλ vj + λ2 vj2 + O |λ|3 |vj |3  . (77) 12 j∈J

j∈J

13

j∈J

P P Note j∈J vj = 0 (from v ∈ H0 ), so the linear term vanishes. Moreover, j∈J vj2 = 12 ∥v∥22 P (conjugate symmetry), and j∈J |vj |3 ≤ 12 ∥v∥∞ ∥v∥22 (Hölder’s inequality). These imply π2 2 λ ∥v∥22 + O(λ3 ∥v∥∞ ∥v∥22 ). (78) 24   By symmetry, we have Pr[Ev ] ≤ 2 Pr ⟨t, v⟩ ≥ 21 ∥v∥22 . For any λ > 0, Using the Markov’s Inequality [26] we get     1 λ 2 2 Pr ⟨t, v⟩ ≥ ∥v∥2 ≤ exp log MG (λ) − ∥v∥2 . (79) 2 2 n o 1 From Eq.(78), choose the optimal λ∗ = min π62 , 2∥v∥ to minimize the exponent. For λ∗ , we ∞ log MG (λ) =

∥v∥2

simplfy the exponent into −C ′ · max{∥v∥2∞ ,1} for constants C, C ′ > 0. We get the unified tail bound as   C ′ ∥v∥22 . (80) Pr[Ev ] ≤ C exp − max{∥v∥∞ , 1} P Now, by union bound, we have Pr[t ∈ / V(0)] ≤ v∈Λ\{0} Pr[Ev ]. Split this sum into two cases. ′

2

term is bounded by Ce−C ∥v∥2 . The sum equals to C(ΘΛ (C ′ )− • ∥v∥∞ ≤ 1. By Eq.(80), P each−β∥v∥ 2 2 is the lattice theta function. 1), where ΘΛ (β) = v∈Λ e For the log-unit lattice, note r = n2 − 1, log det(Λ) = n2 log n + O(n), and then dual lattice √ shortest vector λ1 (Λ∗ ) = Ω(1/ n). So, we get ΘΛ∗ (π 2 /C ′ ) = O(1). Using
the Poisson summation, the total contribution from this case is exp − n2 log n + O(n) . ′

• ∥v∥∞ > 1. Here max{∥v∥∞ , 1} = ∥v∥∞ ≤ ∥v∥2 . So, Eq.(80) implies Pr[Ev ] ≤ Ce−C ∥v∥2 . For short vectors, the Theta function bound gives total contribution exp(− 3n 8 log n + √ n log n) −Ω( O(n log log n)) = o(1). For long vectors, each term is bounded by e , and the number of such vectors is poly(n). So, the total contribution is o(1). Combining both cases, the total failure probability for the Gaussian model is exp(− n2 log n+O(n)). This completes the proof of Part (i). 4.2.2

Proof of Part (ii)

In the real ring model, all embeddings are weakly dependent (not i.i.d.), but the hypothesis (71) 2 guarantees the log-MGF matches the Gaussian model (78) up to a vanishing n o(∥v∥2 )oerror term. We repeat the Chernoff argument from Step 3, with optimal λ′ = min

6 , c0 π 2 ∥v∥∞

the hypothesis. For sufficiently large n, the o(∥v∥22 ) term is negligible. We get   (C ′ − ϵn )∥v∥22 Pr[Ev ] ≤ C exp − , max{∥v∥∞ , 1}

satisfying

(81)

where ϵn = o(1). For large enough n, we have C ′ − ϵn ≥ C ′ /2 > 0. So, the bound is the same exponential decay as the Gaussian case. We then apply the
identical union bound from Step 4: For ∥v∥∞ ≤ 1, the sum is exp − n2 log n + O(n) = o(1); For ∥v∥∞ > 1, the sum is o(1). Thus, the total failure probability is o(1). This completes the proof of Part (ii). Since t ∈ V(0) with an overwhelming probability, the nearest lattice point to t is the origin. Combining with the asymptotic L2 norm from Theorem 4.1, we get √ π √ d(t, Λ) = ∥t∥2 = √ n + o( n), (82) 2 6 which completes the proof. 14

4.3

The L∞ bound and sub-polynomial SGP approximation factor

The approximation factor for the Short Generator Problem (SGP) in the CDPR attack is controlled by the L∞ norm of the CVP residual, i.e., the approximation factor γ = exp(ρ∞ ), where ρ∞ = ∥ΠH0 (L(g)) − ℓ′ ∥∞ and ℓ′ is the nearest lattice point to the target. By Theorem 4.2, ℓ′ = 0 for short generators with an overwhelming probability, so ρ∞ = ∥ΠH0 (L(g))∥∞ . P i Theorem 4.3. Let g = n−1 i=0 ci ζ ∈ R be a non-zero ring element with i.i.d. bounded coefficients ci ∈ {−B, . . . , B} for some fixed B ≥ 1. Then the following result holds √ π √ ∥ΠH0 (L(g))∥∞ = √ 2 ln n + O( ln ln n) (83) 2 6 with a probability 1 − o(1). The corresponding SGP approximation factor satisfies √ π √ γ = exp( √ ln n + O( ln ln n)) = o(nϵ ) 2 3

(84)

for every ϵ > 0. Proof. From the proof of Theorem 4.1, the projected target vector has coordinates tj − t̄ for 1 P an odd j, where tj = log |σj (g)| and t̄ = n j odd tj . By the conjugate-pair relation for 2power cyclotomic fields, we have tm−j = tj and hence tm−j − t̄ = tj − t̄ for all odd js. Let J = {1, 3, . . . , n − 1}. We obtain ∥ΠH0 (L(g))∥∞ = max |tj − t̄| = max |tj − t̄|. j odd

(85)

j∈J

Define Xj := tj − t̄ for j ∈ J. Note each Xj = tj − t̄ is a function of the n independent bounded coefficients c0 , . . . , cn−1 . Fix an index i ∈ {0, . . . , n − 1}, replace ci with c′i such that |ci |, |c′i | ≤ B, while keep all other coefficients fixed. The embedding changes by σk (g ′ ) − σk (g) = (c′i − ci )ζ ik , so |σk (g ′ ) − σk (g)| ≤ |c′i − ci | · |ζ ik | ≤ 2B for all k. Using the Central Limit Theorem [26], √ |σk (g)| = Θ( n) with a probability 1 − o(1). On this high-probability event, using the Meanvalue Theorem [26], we get |σk (g ′ ) − σk (g)| 1
=O √ . (86) ′ min{|σk (g)|, |σk (g )|} n √ WePnow bound the change in Xj = tj − t̄. The change in tj is O(1/ n), and the change in √ t̄ = n1 k odd tk is at most O(1/ n). Thus, the total change in Xj satisfies | log |σk (g ′ )| − log |σk (g)|| ≤

 1  =: ∆i , |Xj′ − Xj | ≤ |t′j − tj | + |t̄′ − t̄| = O √ n

(87)

where ∆i s are the same for all is by symmetry. Using the McDiarmid’s Inequality [36, 20], Xj is a zero-mean sub-Gaussian random variable with the variance n−1

2 σsubG =

1 1X 2 1 ∆i = · n · O = O(1). 4 4 n

(88)

i=0

The low-probability event (|σk (g)| too small) has a total probability o(1). From Lemma 3.2 and Proposition 3.1, we have Var(Xj ) →

π2 24

as n → ∞.

(89) 2

2 2 For any sub-Gaussian random variable X, we get Var(X) ≤ σsubG . So, σsubG ≥ π24 − o(1).

15

From standard extreme-value theory for sub-Gaussian variables [37, 19], we use the variance 2 σ 2 = π24 for the leading-order bound. Now, we use the asymptotic result for the maximum of m independent, identically distributed zero-mean sub-Gaussian random variables with variance σ 2

as √ √ max |Xj | = σ 2 ln m + O( ln ln m)

1≤j≤m

(90)

with probability 1 − o(1). While Xj s are asymptotically independent by√Proposition 3.1, their weak dependence does not affect the leading asymptotic term or the O( ln ln m) error bound for sub-Gaussian sequences [38, 39]. √ In our setting, we have m = |J| = n/2 and σ = π/(2 6). So, we can get p π p max |Xj | = √ 2 ln(n/2) + O( ln ln(n/2)) j∈J 2 6 √ π √ = √ 2 ln n − 2 ln 2 + O( ln ln n). (91) 2 6 √ √ Using the Taylor expansion of a − b = a − 2√b a + O(a−3/2 ) for a fixed b and large a, the p √ √ difference between 2 ln n and 2 ln(n/2) is O(1/ ln n). We thus obtain √ π √ max |Xj | = √ 2 ln n + O( ln ln n), (92) j∈J 2 6 which is the L∞ bound (83). By definition, the CDPR SGP approximation factor is γ = exp(∥ΠH0 (L(g))∥∞ ), as the nearest lattice point is 0 with an overwhelming probability by Theorem 4.2. From Eq. (92), we get √
π √ γ = exp √ 2 ln n + O( ln ln n) 2 6 √
π √ (93) = exp √ ln n + O( ln ln n) . 2 3 To show γ = o(nϵ ) for every ϵ > 0, we take the logarithm of both sides as √  √ π √ log γ = √ ln n + O ln ln n = O( ln n). 2 3

(94)

For any fixed ϵ > 0, we have √  1  log γ O( ln n) = =O √ →0 ϵ ln n ln n ln n

(95)

as n → ∞. This implies log γ = o(ϵ ln n) for every ϵ > 0, or γ = exp(o(ϵ ln n)) = o(nϵ ). This completes the proof. For the ML-KEM (standard parameter set n = 256), we have ln 256 = 8 ln 2 ≈ 5.545, √ π so ln 256 ≈ 2.355. The leading coefficient 2√ ≈ 0.9069. The leading term of log γ is 3 0.9069 × 2.355 ≈ 2.136. So, the resulting approximation factor is γ ≈ exp(2.136) ≈ 8.47 ≈ 23.1 .

5

The Coarse Lattice Theorem and Babai Recovery

This section proves two complementary results about Babai’s algorithm on the log-unit lattice. The Coarse Lattice Theorem shows Babai returns a zero vector for all structured targets, an unconditional result that does not require the Voronoi containment of Theorem 4.2. The Babai Capture Theorem shows that Babai exactly recovers lattice-vector perturbations of arbitrary size, so the CDPR pipeline succeeds whenever the balanced target maps to zero. 16

5.1

The Coarse Lattice Theorem

√ The term coarse refers to a scale mismatch: the Gram-Schmidt norms of Λ are Ω( n), while the per-component standard deviation of the structured target is O(1). When the lattice space greatly exceeds the target’s fluctuations in every GS direction, the target sits in a tiny neighborhood of the origin, and Babai’s rounding step always gives zero. Theorem 5.1. Let Λ be the rank-r log-unit lattice with Gram-Schmidt basis {b′i }ri=1 , t ∈ H0 be a random vector with independent, zero-mean, sub-Gaussian components with per-component variance σt2 . Suppose the coarseness condition holds min1≤i≤r ∥b′i ∥22 = ω(log n). σt2

(96)

Then the Babai’s nearest-plane algorithm returns the zero lattice vector with probability 1 − o(1), and the Babai residual equals t as dBabai (t, Λ)2 = ∥t∥22 = nσt2 .

(97)

Proof. From Definition 2.6, the Babai’s algorithm processes the GS basis in reverse order i = r, r − 1, . . . , 1. At each step i, it computes the projection coefficient j ⟨t − P cj bj , b′ ⟩ m i j>i ci = . (98) ∥b′i ∥22 P The algorithm outputs v = ri=1 P ci bi with residual e = t − v. If cj = 0 for all j > i, then j>i cj bj = 0, and the projection coefficient at step i reduces to µi =

⟨t, b′i ⟩ . ∥b′i ∥22

(99)

The rounded coefficient is ci = ⌊µi ⌉. This equals zero if and only if |µi | < 12 . For case i = r, there is no sum over j > r, so µr is given by Eq. (99). For i < r, assume cj = 0 for all j > i. Eq. (99) holds for step i. So, Babai’s algorithm returns 0 if and only if |µi | < 12 for every i ∈ {1, . . . , r}. This can be verified for each i. So, the problem reduces to show |µi | < 21 simultaneously for all i. We now bound |µi | using the sub-Gaussian assumption on t. Rewrite the inner product as ⟨t, b′i ⟩ =

n X

tj (b′i )j ,

(100)

j=1

where tj s are the components of t and (b′i )j s are the components of the i-th GS vector. By assumption, tj s are independent, zero-mean, sub-Gaussian random variables with common parameter σt2 . Consider he sub-Gaussian summation property ([19]): P if X1 , . . . , Xn are independent sub-Gaussian variables with parameters σ12 , . . . , σn2 , then j aj Xj is sub-Gaussian with P parameter j a2j σj2 . So, for aj = (b′i )j and σj2 = σt2 for all j, we get ⟨t, b′i ⟩ ∼ subG 0, σt2

n X

(b′i )2j = subG 0, σt2 ∥b′i ∥22 .

(101)

j=1

Dividing by ∥b′i ∥22 , the projection coefficient is given by µi =

 ⟨t, b′i ⟩ σt2  ∼ subG 0, . ∥b′i ∥22 ∥b′i ∥22 17

(102)

π ≈ 0.64 Table 1: Verification of the coarseness condition for 2k -th cyclotomic fields. σt = 2√ 6 is the per-component standard deviation of structured p targets from Theorem 4.1. The ratio mini ∥b′i ∥22 /n decreases with k, implying mini ∥b′i ∥2 ∼ n/ log n (unproved).

k

n

min∥b′i ∥2

σS

σt min∥b′i ∥2

4 6 8 10 12

8 32 128 512 2048

2.00 3.18 5.42 9.58 17.4

0.64 0.64 0.64 0.64 0.64

0.32 0.20 0.12 0.07 0.04

The sub-Gaussian parameter of µi is the given by σµ2 i = σt2 /∥b′i ∥22 , which is the ratio of the target’s variance to the squared GS norm. So, for any t ≥ 0 we obtain the sub-Gaussian tail bound as  t2  Pr[|µi | ≥ t] ≤ 2 exp − 2 . (103) 2σµi Setting t = 12 (the rounding threshold), we get 
(1/2)2  ∥b′i ∥22
Pr |µi | ≥ 12 ≤ 2 exp − . = 2 exp − 2 · σt2 /∥b′i ∥22 8σt2

(104)

By the coarseness condition (96), we get ∥b′i ∥22 /σt2 = ω(log n) for every i. Hence, the exponent satisfies ∥b′i ∥22 /(8σt2 ) = ω(log n), and Pr[|µi | ≥ 12 ] ≤ 2 exp(−ω(log n)) = o(1/n),

(105)

where the last uses exp(−ω(log n)) = o(1/nc ) for every constant c > 0. As there are r ≤ n/2 GS directions, the event that Babai does not return 0 is {∃i : |µi | ≥ 1/2}. So, by the union bound, we have r X Pr[∃i : |µi | ≥ 21 ] ≤ Pr[|µi | ≥ 12 ] ≤ r · 2 exp(−ω(log n)) i=1

n · o(1/n) = o(1). (106) 2 Here, the factor n/2 is absorbed as the exponential decay is super-polynomial. P Finally, all ci = 0 with a probability 1−o(1). The Babai output is given by v = ri=1 0·bi = 0, and the residual is e = t − 0 = t. So, we get dBabai (t, Λ)2 = ∥t∥22 . This means for structured targets with i.i.d. sub-Gaussian components of variance σt2 , we get Eq. (97) as the law of large numbers gives ∥t∥22 ≈ nσt2 . ≤

The proof supposes that the components tj of t are independent. For the real structured target t = ΠH0 (L(g)), the components are not exactly independent, but asymptotically independent by Proposition 3.1 and Theorem 4.3. The sub-Gaussian tail bound (104) holds for this model. Hence, the Coarse Lattice Theorem applies to the real model. For structured targets, we have σt2 = π 2 /24 ≈ 0.41 (Theorem 4.1). p The GS norms of the √ ′ log-unit lattice satisfy mini ∥bi ∥2 = ω( log n), growing roughly as n/ log n (see Table 1). Hence, we have mini ∥b′i ∥22 = ω(log n), σt2

(107)

which is sufficient for the union bound in the proof. Even for worst-case targets with σt2 ∼ log n, the ratio remains ω(1). So, the coarseness condition is satisfied. 18

5.2

Infinite capture radius

In the CDPR pipeline, the target is not L(g0 ) but L(g) = L(g0 ) + L(ϵ), where L(ϵ) ∈ Λ can be an arbitrarily large lattice vector. The following theorem shows that Babai’s algorithm can resolve this problem. Theorem 5.2. Let Λ ⊂ Rn have basis B ∈ Rn×r with QR decomposition B = QR. For any target t0 ∈ Rn and lattice vector v = Bc (c ∈ Zr ), let v0 = Bx0 be the Babai output for t0 , and v′ = Bx′ for t = t0 + v. Then we have v ′ = v + v0 .

(108)

Proof. It is easy to show the nearest-integer rounding function ⌊·⌉ : R → Z satisfies ⌊a + b⌉ = a + ⌊b⌉

(109)

for all a ∈ Z, b ∈ R. Moreover, the basis B = QR with Q ∈ Rn×r (orthonormal columns) and R ∈ Rr×r (upper triangular, positive diagonal). Babai’s algorithm computes • β = QT t ∈ Rr • For i = r, r − 1, . . . , 1: xi =

j βi − P

j>i Rij xj

Rii

m

.

(110)

• Output v = Bx = QRx. Here, the columns of Q are the normalized GS vectors, Qi = b′i /∥b′i ∥2 , and Rii = ∥b′i ∥2 , Rji = µij ∥b′j ∥2 for j < i. The quantity βi = qTi t = ⟨t, b′i ⟩/∥b′i ∥2 is the projection of t onto b′i , scaled by ∥b′i ∥2 . Equation (110) is equivalent to the GS back-substitution in Definition 2.6. Let t = t0 + v = t0 + Bc with c ∈ Zr . The projected vector is given by β = QT t = QT t0 + QT Bc = β (0) + Rc,

(111)

where β (0) = QT t0 is the projection P of the unperturbed target, and we have used QT B = R. Since R is upper triangular, (Rc)i = j≥i Rij cj depends only on ci , ci+1 , . . . , cr . For i = r, the back-substitution at the top step gives jβ m r x′r = . (112) Rrr (0)

(0)

From Eq. (111), we get βr = βr + (Rc)r = βr + Rrr cr since R is upper triangular, where the only term in (Rc)r involving row r is Rrr cr . Dividing by Rrr , we get (0)

(0)

βr βr + Rrr cr βr = = cr + . Rrr Rrr Rrr

(113)

Since cr ∈ Z, Eq.(109) gives x′r =

j

(0)

(0)

jβ m βr m r cr + = cr + = cr + x(0) r . Rrr Rrr (0)

For i < r, assume x′j = cj + xj

(114)

for all j > i. At step i, Babai’s algorithm computes j βi − P Rij x′ m j j>i x′i = . (115) Rii 19

(0)

Using βi = βi

(0)

+ (Rc)i from Eq.(111) and x′j = cj + xj , we then get X X X (0) (0) βi − Rij x′j = βi + (Rc)i − Rij cj − Rij xj . j>i

Note (Rc)i =

j>i

P

j≥i Rij cj = Rii ci +

βi −

X

P

(116)

j>i

j>i Rij cj . So, we have (0)

Rij x′j = Rii ci + (βi

−

j>i

X

(0)

Rij xj ).

(117)

j>i

Dividing by Rii , we then get βi −

′ j>i Rij xj

(0)

P

Rii

= ci +

βi

−

(0) j>i Rij xj

P

.

(118)

= ci + xi .

(119)

Rii

Since ci ∈ Z, Eq.(109) gives (0)

x′i =

j

ci +

βi

−

P

(0) m j>i Rij xj

Rii

(0)

This completes the induction. (0) By induction, x′i = ci + xi for all i ∈ {1, . . . , r}, i.e., x′ = c + x0 . Applying the basis matrix gives v′ = Bx′ = B(c + x0 ) = Bc + Bx0 = v + v0 .

(120)

Especially, if v0 = 0, then v′ = v, i.e., Babai recovers the lattice vector v. This completes the proof.

5.3

Application to the CDPR pipeline

We combine Theorems 5.1 and 5.2 with the CDPR attack. (1) PIP output. Suppose the quantum PIP algorithm produces a generator g = g0 ϵ, where g0 is a short generator and ϵ ∈ R× is a unit. In the log-embedding, it gives L(g) = L(g0 ) + L(ϵ),

L(ϵ) ∈ Λ.

(121)

(2) Babai’s algorithm on the balanced target (Theorem 5.1). The balanced target is t0 = ΠH0 (L(g0 )). By the Coarse Lattice Theorem 5.1, Babai’s algorithm returns v0 = 0 for t0 with a probability 1 − o(1). (3) Babai’s algorithm on the PIP output (Theorem 5.2). The real target is ΠH0 (L(g)) = t0 + L(ϵ) with L(ϵ) ∈ Λ. By the Capture Theorem 5.2 with v = L(ϵ) and v0 = 0, Babai’s output is ΠH0 (L(g)) = L(ϵ) + 0 = L(ϵ).

(122)

(4) Short generator recovery. From L(ϵ), the unit ϵ is reconstructed. The short generator is then g ′ = g · ϵ−1 = g0 . The approximation factor is given by p γ = exp(∥ΠH0 (L(g0 ))∥∞ ) = exp(O( log n)), (123) using Theorem 4.3 for the L∞ norm of the balanced target. This result is unconditional except for the probabilistic statement in step (2) that the balanced target maps to zero. This holds with probability 1 − o(1) by the Coarse Lattice Theorem 5.1, using only the sub-Gaussianity of the log-embedding. 20

6

The Trigamma Theorem for Module Lattices

We now extend our ideal-lattice analysis to the module lattice setting. The CDPR attack on module lattices reduces the Module Short Generator Problem (Module-SGP) to an ideal-lattice SGP on the module’s determinant ideal (Part II).

6.1

The Trigamma Theorem

ML-KEM deploys module lattices of rank d ∈ {2, 3, 4} over the cyclotomic ring R = Z[ζ256 ]. For a general module with basis matrix B ∈ Rd×d , the CDPR attack reduces the module SGP to an ideal SGP on the determinant ideal (det B) ⊂ R. The key question reduces to: what is the CVP distance for the shortest generator of this determinant ideal? From Theorems 4.1 and 4.3, the CVP distance and resulting SGP approximation factor are controlled by the per-component variance σg20 = n1 ∥ΠH0 (L(g0 ))∥22 , where g0 = det B is the shortest generator of the determinant ideal. Theorem 6.1. Let R = Z[ζ2k ] be the 2k -th cyclotomic ring with n = 2k−1 , and B = (bij ) ∈ Rd×d be a module basis matrix whose entries are independent ring elements. Each entry bij has i.i.d. zero-mean coefficients with variance σc2 and finite fourth moment, with mutual independence across all entries. Define g0 = det(B) ∈ R and the per-component variance σg20 = n1 ∥ΠH0 (L(g0 ))∥22 . Then, d X 2 p 1 ψ ′ (j) σg0 → − 4 j=1

as n → ∞,

(124)

where ψ ′ (s) denotes the trigamma function. Proof. Note every canonical embedding σj : R → C is a ring homomorphism, so it commutes with the determinant operation for matrices over R. For any j, we have σj (g0 ) = σj (det B) = det(σj (B)),

(125)

where σj (B) ∈ Cd×d denotes the matrix obtained by applying σj entry-wise to B. Taking the modulus and logarithm of both sides, we obtain log |σj (g0 )| = log | det(σj (B))|.

(126)

Note each entry of B is a random ring element with i.i.d. zero-mean coefficients of variance σc2 . Applying Proposition 3.1 entry-wise, for any fixed non-conjugate index j ∈ J, the normalized embedded matrix converges in distribution as p 1 d σj (B) − → M (j) , τ = nσc2 , τ

(127)

where M (j) is a d × d matrix with i.i.d. standard complex Gaussian entries CN (0, 1). Moreover, from the joint CLT, the limiting matrices {M (j) }j∈J are mutually independent, as the embeddings for different non-conjugate indices are asymptotically independent by Proposition 3.1. Let M be a d × d matrix with i.i.d. CN (0, τ 2 ) entries. Consider its QR decomposition M = QR. A classical result in random matrix theory gives the exact distribution of the 2 /τ 2 are independent, and has squared diagonal entries of R [40, 41]: the normalized variables Rii R2

Gamma distributions as τ 2ii ∼ Γ(d − i + 1, 1) for i = 1, . . . , d, where Γ(k, 1) denotes the Gamma distribution with shape parameter k and rate parameter 1.

21

Since Q is unitary, we have | det Q| = 1, so | det M | = both sides, we decompose the log-determinant as log | det M | =

d X

log Rii =

i=1

Qd

i=1 Rii .

Taking the logarithm of

d X 1 i=1

d   1X 2 log Rii = d log τ + log Wi , 2 2

(128)

i=1

2 /τ 2 ∼ Γ(d−i+1, 1). where we have defined the independent normalized random variables Wi := Rii The term d log τ is a constant, as it depends only on the scaling factor τ and the module rank d. Note the deterministic term d log τ does not contribute to the variance of log | det M |. By the independence of the Wi , we get the variance as d

1X Var(log | det M |) = Var(log Wi ). 4

(129)

i=1

For a Gamma-distributed random variable W ∼ Γ(k, 1), the logarithmic moments are given by: E[log W ] = ψ(k) and Var(log W ) = ψ ′ (k), where ψ is the digamma function and ψ ′ is the trigamma function. Using ki = d − i + 1 and re-indexing the sum with j = d − i + 1, we obtain d

1X ′ Var(log | det M |) = ψ (j). 4

(130)

j=1

This variance is independent of τ 2 , and hence independent of σc2 and the modulus q. For any fixed finite collection of different indices j1 , . . . , js ∈ J, the normalized matrices 1 τ σjℓ (B) converge jointly in distribution to independent d×d standard complex Gaussian matrices. We apply the continuous mapping theorem to the function f (M ) = log | det(M )| and obtain d

(log |σjℓ (g0 )|)sℓ=1 − → (log | det M (jℓ ) |)sℓ=1 ,

(131)

where the right-hand side consists of i.i.d. copies of log | det M |. Finally, applying Theorem 4.1 to the determinant element g0 , the per-component variance σg20 converges in probability to the variance of a single centered log-determinant component. Since the components are asymptotically i.i.d. with the distribution of log | det M | − E[log | det M |], we obtain 

p σg20 → − Var

d  1X log | det M | = ψ ′ (j), 4

(132)

j=1

which completes the proof. Across all valid centered distributions, the limit (124) depends only on the module rank d. Table 2 confirms this numerically: σg0 is stable across all tested values of σc corresponding to moduli q ∈ {3, 11, 101, 3329, 65537}.

6.2

ML-KEM Security Analysis

We now combine all results to analyze the security of ML-KEM. ML-KEM is the NISTstandardized post-quantum public-key encryption scheme, whose security relies on the hardness of Module-LWE over the cyclotomic ring R = Z[ζ256 ] with module ranks d ∈ {2, 3, 4} (corresponding to ML-KEM-512, ML-KEM-768, and ML-KEM-1024, respectively), see Tables 3 and 4. For ML-KEM-1024 (d = 4, n = 256), the Trigamma Theorem 6.1 gives σg0 ≈ 0.861 in the asymptotic Gaussian limit. With finite-n ring-based computations (Table 2) we get σg0 ≈ 1.03

22

Table 2: Trigamma Theorem 6.1 predictions, Monte Carlo simulations, and ring-based computations for k = 9, n = 256, q = 3329. Ring values match the Gaussian prediction within ±2% across all tested 3}). ρ∞ values √distributions (uniform mod-q, CBD η = 2, Gaussian, U {−3, . . . , √ include the O( ln ln n) ≈ 1.3 extreme-value correction over the leading term σd 2 ln n. d

σg0 (Theory)

Monte Carlo

Ring (q = 3329)

ρ∞ (n = 256)

1 2 3 4

0.641 0.757 0.819 0.861

0.641 0.761 0.818 0.863

0.637 0.751 0.814 0.857

2.51 2.56 2.78 2.83

Table 3: ML-KEM security summary against the CDPR attack. γSGP is the per-ideal SGP factor from Part III. γ = αd · γSGP composes this with the module reduction factor from Part II. Scenario CDPR original [1] Parts I+II base Part III (d = 4) ∗

γSGP (bits)

γ = αd γSGP (bits)

Status

Secure?

254 254 24–5

Θ(254 ) Θ(254 ) O(1) · 24–5

Proved Proved Proved

Yes Yes Conditional∗

Conditional on the CLT hypothesis (numerically verified for k ∈ {4, . . . , 12}, and quantum PIP algorithm.

for the ML-KEM modulus q = 3329. Applying Theorem 4.3 with σ = σg0 , we get SGP approximation factor (  √  exp(0.861 × 3.33) ≈ 24.1 (Gaussian limit), γSGP ≈ exp σg0 2 ln n = (133) exp(1.03 × 3.33) ≈ 24.9 (finite-n ring value). Both are below q/2 ≈ 210.7 threshold required for the CDPR attack to succeed. The security of ML-KEM against this attack no longer depends on the SGP approximation factor, but instead rests on the quantum gate cost of the Biasse-Song PIP algorithm [4], which will be analyzed in the next Part. Note γSGP is the per-ideal SGP factor for the module’s determinant ideal. The total ModuleSVP approximation factor is γ = αd · γSGP , where αd is the module reduction factor √ from Part II of this series. For MLWE-distributed module bases (Part II), we have αd = C = O(1), so the total approximation factor remains γ = O(1) · 24−5 .

7

Conclusion

We have proved several results for the short generator problem in 2-power cyclotomic fields. √ 2 constant π/(2 6). Theorem 4.3 yields the sub-polynomial Theorem 4.1 identifies the exact L √ SGP factor exp(O( log n)). Theorem 4.2 shows the nearest lattice point is the origin. Numerical verification confirms the result for all tested parameters k ∈ {4, . . . , 12}. Theorem 5.2 strengthens the Babai’s recovery to be unconditional for the cyclotomic-unit basis. The Coarse Lattice Theorem 5.1 explains the reason why Λ is too coarse for structured targets. The Trigamma Theorem 6.1 resolves the ML-KEM question, i.e., σg0 = O(1) for module determinant ideals, independently of q. Part I proved h+ k = 1 unconditionally for k ≤ 12. Part II reduced the module-SVP polynomial factor from nO(d) to a universal constant αd = O(1) independent of d under a balance hypothesis automatic for MLWE inputs. Part III identifies the CDPR exponent as being controlled by σg0 . For ML-KEM-1024 (d = 4, n = 256), the SGP factor is γSGP ≈ 24−5 , see Table 2. The module reduction adds a factor αd = O(1) from Part II, independent of d. The combined approximation 23

Table 4: Cumulative improvements to the CDPR attack analysis across Parts I–III. Component Class number (Part I) Module reduction (Part II) Sign discrepancy (Part II) SGP approx factor (Part III) σg0 (Part III) Lattice geometry (Part III) True security bottleneck

Prior State

This Work

h+ = 1 conditional ( n2√ )d−1 Θ( nk) √ exp(Õ( n)) √ Θ( n) assumed Hard CVP on Λ Approximation factor

Proved√for k ≤ 12 αd = C = O(1) δ ′ ≈ 0.44 = O(1) √ γSGP = exp(O( log n)) O(1), q-independent Babai’s algorithm is trivial Quantum PIP gate cost

quality is sub-polynomial and sufficient for the attack, so ML-KEM’s security rests on the quantum gate cost of PIP [4].

Acknowledgments [Acknowledgments will be added in the final version.]

References [1] Ronald Cramer, Léo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals in cyclotomic rings. In Advances in Cryptology-EUROCRYPT 2016, volume 9666 of Lecture Notes in Computer Science, pp.559-585. Springer, 2016. [2] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Short stickelberger class relations and application to Ideal-SVP. In Advances in Cryptology-EUROCRYPT 2017, volume 10210 of Lecture Notes in Computer Science, pp.324-348. Springer, 2017. [3] Ronald Cramer, Léo Ducas, and Benjamin Wesolowski. Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time. Journal of the ACM, 68: 1-26, 2021. [4] Jean-François Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.893-902. SIAM, 2016. [5] Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehlé. Approx-SVP in ideal lattices with pre-processing. In Advances in Cryptology-EUROCRYPT 2019, volume 11477 of Lecture Notes in Computer Science, pp.685-716. Springer, 2019. [6] 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 Lecture Notes in Computer Science, pp.324-348. Springer, 2023. [7] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75: 565-599, 2015. [8] Guilhem Mureau, Alice Pellet-Mary, Georgii Pliatsok, and Alexandre Wallet. Cryptanalysis of rank-2 module-lip in totally real number fields. In Advances in Cryptology-EUROCRYPT 2024, pp.226-255. Springer, 2024.

24

[9] Bill Allombert, Alice Pellet-Mary, and Wessel van Woerden. Cryptanalysis of rank-2 modulelip: A single real embedding is all it takes. In Advances in Cryptology-EUROCRYPT 2025, volume 15602 of Lecture Notes in Computer Science, pp.184-212. Springer, 2025. [10] 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 Lecture Notes in Computer Science, pp.154-183. Springer, 2025. [11] Léo Ducas, Lynn Engelberts, and Paola de Perthuis. Predicting module-lattice reduction. In Advances in Cryptology-ASIACRYPT 2025, Lecture Notes in Computer Science, pp.133-166. Springer, 2025. [12] Laszlo Babai. On Lovasz lattice reduction and the nearest lattice point problem. Combinatorica, 6: 1-13, 1986. [13] Arjen K. Lenstra, Hendrik W. Lenstra, and Laszlo Lovasz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261: 515-534, 1982. [14] Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53: 201-224, 1987. [15] Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within Mordell’s inequality. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp.207-216. ACM, 2008. [16] Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2n time using discrete Gaussian sampling. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp.733-742. ACM, 2015. [17] Patrick Billingsley. Probability and Measure. Wiley, 3rd edition, 1995. [18] William Feller. An Introduction to Probability Theory and Its Applications, volume 2, Wiley, 2nd edition, 1971. [19] Roman Vershynin. High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018. [20] Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013. [21] Terence Tao. Topics in Random Matrix Theory. American Mathematical Society, 2012. [22] Milton Abramowitz and Irene A. Stegun. Handbook of Mathematical Functions. Dover, 1964. [23] Jürgen Neukirch. Algebraic Number Theory, volume 322 of Grundlehren der mathematischen Wissenschaften. Springer, 1999. [24] Warren Sinnott. On the Stickelberger ideal and the circular units of a cyclotomic field. Annals of Mathematics, 108: 107-134, 1978. [25] Lawrence C. Washington. Introduction to Cyclotomic Fields, volume 83, Graduate Texts in Mathematics. Springer, 2nd edition, 1997. [26] Rick Durrett. Probability: Theory and Examples. Cambridge University Press, 5th edition, 2019.

25

[27] Harald Cramér and Herman Wold. Some theorems on distribution functions. Journal of the London Mathematical Society, s1-11: 290-294, 1936. [28] Patrick Billingsley. Convergence of Probability Measures. Wiley, New York, 2nd edition, 1999. [29] Valentin V. Petrov. Limit Theorems of Probability Theory. Oxford University Press, 1995. [30] Andrew C. Berry. The accuracy of the Gaussian approximation to the sum of independent variates. Transactions of the American Mathematical Society, 49: 122-136, 1941. [31] Carl-Gustav Esseen. On the Liapounoff limit of error in the theory of probability. Arkiv för matematik, astronomi och fysik, 28A(9):1–19, 1942. [32] Edmund T. Whittaker and George N. Watson. A Course of Modern Analysis. Cambridge University Press, 1996. [33] https://dlmf.nist.gov/.Release 1.1.12, 2023; Chapter 5 (Gamma Function), Sec. 5.15 (Polygamma Functions). [34] Józef Marcinkiewicz and Antoni Zygmund. Sur les fonctions indépendantes. Fundamenta Mathematicae, 29: 60-90, 1937. [35] Victor H. de la Pe na and Evarist Giné. Decoupling: From Dependence to Independence. Springer, New York, 1999. [36] Colin McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics 1989, volume 141 of London Mathematical Society Lecture Note Series, pp.148-188. Cambridge University Press, 1989. [37] M. R. Leadbetter, Georg Lindgren, and Holger Rootzén. Extremes and Related Properties of Random Sequences and Processes. Springer, New York, 1983. [38] Simeon M. Berman. Limit theorems for the maximum term in stationary sequences. Annals of Mathematical Statistics, 35: 502-516, 1964. [39] Martin J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge University Press, 2019. [40] Robb J. Muirhead. Aspects of Multivariate Statistical Theory. Wiley, New York, 1982. [41] Peter J. Forrester. Log-Gases and Random Matrices. Princeton University Press, 2010.

26