pith. sign in

arxiv: 2605.17404 · v1 · pith:UA3IMYCVnew · submitted 2026-05-17 · 💻 cs.DS · cs.CR· math.NT· math.ST· quant-ph· stat.TH

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

Ming-Xing Luo This is my paper

Pith reviewed 2026-05-19 22:55 UTC · model grok-4.3

classification 💻 cs.DS cs.CRmath.NTmath.STquant-phstat.TH
keywords module latticesCVPlog-unit latticecyclotomic fieldsshort generator problemML-KEMVoronoi cellBabai's algorithm
0
0 comments X

The pith

The L² CVP distance from a random short ring element to the log-unit lattice converges to π/(2√6) √n as the dimension n tends to infinity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper aims to characterize the geometric position of typical short elements relative to the log-unit lattice in cyclotomic number fields of power-of-two conductor. It establishes that the Euclidean distance in the log embedding converges to a precise constant multiple of the square root of the field degree. This placement inside the Voronoi cell of the zero vector allows exact identification of the lattice point as the origin. When merged with results from prior parts of the series, the finding tightens the approximation factor for solving the short generator problem from exponential in the square root of n down to sub-polynomial size, which directly impacts the provable security of module-lattice key encapsulation mechanisms such as ML-KEM.

Core claim

The paper proves that the L² CVP distance from a random short ring element to the log-unit lattice of Q(ζ_{2^k}) converges to π/(2√6) √n as n=2^{k-1}→∞. This target lies inside the Voronoi cell of the origin for k≥4. The L^∞ norm yields O(√log n), giving a sub-polynomial factor for the Short Generator Problem. A Coarse Lattice Theorem shows Babai's algorithm returns zero for structured targets while recovering unit perturbations. The Trigamma Theorem proves module determinant ideals have intrinsic imbalance σ_{g0}=O(1) independent of q. Combined with Parts I and II, the CDPR factor for ML-KEM reduces from exp(O(√n)) to sub-polynomial.

What carries the argument

The log-unit lattice arising from the logarithmic embedding of the units in the ring of integers of Q(ζ_{2^k}), together with the modeling of short ring elements as having sub-Gaussian coordinates in that embedding.

If this is right

  • The structured target vector lies in the interior of the Voronoi cell of the origin when k is at least 4.
  • Babai's algorithm applied to these targets returns the zero vector while still recovering arbitrary unit multiples exactly.
  • The infinity-norm analysis produces an approximation factor of order square root of log n for the short generator problem.
  • The Trigamma Theorem establishes that the imbalance parameter for module determinant ideals remains bounded by a constant independent of the modulus q.
  • The CDPR approximation factor required in security reductions for ML-KEM drops from exponential in sqrt(n) to sub-polynomial.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the random short element model accurately captures real distributions used in cryptography, then current security estimates for module lattice schemes may need adjustment due to the improved factor.
  • Numerical verification of the distance convergence for successively larger values of k would provide direct evidence supporting or refuting the asymptotic claim.
  • The Coarse Lattice Theorem and Voronoi membership suggest that certain structured instances of CVP admit unusually simple solutions compared to generic cases.

Load-bearing premise

The logarithmic embeddings of random short ring elements behave as independent sub-Gaussian random variables so that their Euclidean norm and maximum coordinate follow the derived concentration bounds and yield membership in the Voronoi cell.

What would settle it

Direct computation of the average L2 distance over many random short elements for large k and observation of whether the value approaches or diverges from π/(2√6) times sqrt(n).

read the original abstract

We prove that the $L^2$ CVP distance from a random short ring element to the log-unit lattice of $\Q(\zeta_{2^k})$ converges to $\frac{\pi}{2\sqrt{6}}\sqrt{n}$ as $n=2^{k-1}\to\infty$. We then show that this target lies inside the Voronoi cell of the origin for $k\ge 4$. For the $L^\infty$ norm, the maximum over $n$ sub-Gaussian coordinates yields $O(\sqrt{\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 $\sigma_{g_0}=O(1)$ independent of the modulus $q$. Finally, combined with Parts I and II, we reduce the CDPR factor for ML-KEM from $\exp(\tO(\sqrt{n}))$ to a sub-polynomial value.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The manuscript proves that the L² CVP distance from a random short ring element to the log-unit lattice of Q(ζ_{2^k}) converges to π/(2√6) √n as n=2^{k-1}→∞. It shows that this target lies 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. The paper introduces a Coarse Lattice Theorem stating that Babai's algorithm returns zero for all structured targets yet recovers unit perturbations of arbitrary size, and a Trigamma Theorem proving an intrinsic imbalance σ_{g0}=O(1) independent of the modulus q for module determinant ideals. Combined with Parts I and II, these results reduce the CDPR factor for ML-KEM from exp(Õ(√n)) to a sub-polynomial value.

Significance. If the central convergence result and Voronoi-cell membership hold under the stated modeling assumptions, the work would materially strengthen the concrete security analysis of module-lattice schemes such as ML-KEM by replacing an exponential-in-√n approximation factor with a sub-polynomial one. The explicit constant π/(2√6) and the two named theorems (Coarse Lattice and Trigamma) supply parameter-free geometric information about the log-unit lattice that could be used directly in security estimates and parameter selection.

major comments (3)
  1. [Abstract and L^∞ paragraph] Abstract and L^∞ paragraph: The claimed L²-distance limit and the subsequent Voronoi-cell membership rest on the assertion that log-embeddings of random short ring elements are effectively i.i.d. sub-Gaussian after projection onto the trace-zero hyperplane. The cyclotomic minimal polynomial induces linear dependencies among the complex embeddings; these may produce non-negligible covariances in the log-space that survive the trace-zero projection and alter both the variance of the squared distance and the probability that the target lies inside the Voronoi cell of the origin. A quantitative bound on the total variation or covariance error in the large-n limit is required to justify the exact constant π/(2√6).
  2. [Reduction paragraph] Reduction paragraph (combined with Parts I and II): The reduction of the CDPR factor to sub-polynomial size is obtained by chaining the L^∞ bound O(√log n) with the Coarse Lattice Theorem. Because the L^∞ bound itself is derived from the same sub-Gaussian coordinate model whose independence is questioned above, any correction to the covariance structure would propagate directly into the final approximation factor and must be re-derived or bounded.
  3. [Trigamma Theorem] Trigamma Theorem statement: The claimed intrinsic imbalance σ_{g0}=O(1) independent of q is presented as a consequence of the module-determinant geometry. The proof sketch (or lack thereof) does not indicate how the trace-zero projection and the algebraic relations among embeddings are controlled when the ideal is scaled by an arbitrary modulus q; an explicit error term or reference to a supporting lemma is needed.
minor comments (2)
  1. [Preliminaries] The distribution of the 'random short ring element' is invoked repeatedly but never given a precise probability measure or generating procedure; a formal definition (e.g., uniform over elements of bounded L^∞ norm in the ring of integers) should appear in the preliminaries.
  2. [L²-distance derivation] The manuscript refers to 'sub-Gaussian coordinates' without stating the precise sub-Gaussian parameter or tail bound used in the variance calculation leading to the constant π/(2√6); adding this parameter would make the derivation self-contained.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive report. We address each major comment below, indicating where we will revise the manuscript to strengthen the exposition and where we maintain the original claims under the stated modeling assumptions.

read point-by-point responses

  1. Referee: [Abstract and L^∞ paragraph] The claimed L²-distance limit and the subsequent Voronoi-cell membership rest on the assertion that log-embeddings of random short ring elements are effectively i.i.d. sub-Gaussian after projection onto the trace-zero hyperplane. The cyclotomic minimal polynomial induces linear dependencies among the complex embeddings; these may produce non-negligible covariances in the log-space that survive the trace-zero projection and alter both the variance of the squared distance and the probability that the target lies inside the Voronoi cell of the origin. A quantitative bound on the total variation or covariance error in the large-n limit is required to justify the exact constant π/(2√6).

    Authors: The cyclotomic minimal polynomial does induce linear dependencies, but the trace-zero projection removes the dominant all-ones correlation, and the remaining covariances vanish asymptotically by equidistribution of Galois orbits. The constant π/(2√6) is obtained from the expected squared Euclidean norm of a standard Gaussian vector on the (n-1)-dimensional hyperplane; this limit is stable under o(1) perturbations to the covariance matrix. We will add an explicit lemma bounding the total-variation distance between the projected log-embedding distribution and the i.i.d. sub-Gaussian model by O(1/√n), which is sufficient to preserve both the exact limit and the Voronoi-cell membership for k ≥ 4. revision: yes

  2. Referee: [Reduction paragraph] The reduction of the CDPR factor to sub-polynomial size is obtained by chaining the L^∞ bound O(√log n) with the Coarse Lattice Theorem. Because the L^∞ bound itself is derived from the same sub-Gaussian coordinate model whose independence is questioned above, any correction to the covariance structure would propagate directly into the final approximation factor and must be re-derived or bounded.

    Authors: The Coarse Lattice Theorem is a deterministic statement about Babai’s algorithm on structured targets and does not rely on distributional assumptions. For the L^∞ bound, even under logarithmic-degree algebraic dependence the maximum of n sub-Gaussian coordinates remains O(√log n) with high probability by standard concentration results for weakly dependent variables. The sub-polynomial character of the resulting approximation factor is therefore unaffected. We will insert a short remark citing the appropriate dependence-aware tail bound to make this explicit. revision: partial

  3. Referee: [Trigamma Theorem] The claimed intrinsic imbalance σ_{g0}=O(1) independent of q is presented as a consequence of the module-determinant geometry. The proof sketch (or lack thereof) does not indicate how the trace-zero projection and the algebraic relations among embeddings are controlled when the ideal is scaled by an arbitrary modulus q; an explicit error term or reference to a supporting lemma is needed.

    Authors: The imbalance σ_{g0} is defined after normalization by the module determinant; scaling the ideal by q multiplies all embeddings by the same factor and therefore cancels in the normalized log-space. The trace-zero projection is orthogonal with respect to the trace form and introduces no additional q-dependence. We will expand the proof of the Trigamma Theorem to include an explicit error term O(1/q + 1/n) and add a reference to the supporting determinant calculation in Part II. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation is a direct proof under stated modeling assumptions

full rationale

The paper states a theorem proving convergence of the L² CVP distance to π/(2√6)√n for the modeled random short ring element, followed by Voronoi cell membership and norm bounds, all presented as derived from lattice geometry and sub-Gaussian tail estimates in the trace-zero hyperplane. No step reduces a claimed prediction to a fitted parameter by construction, renames a known result, or loads the central limit on a self-citation whose content is itself unverified. The model of random short ring elements is an explicit assumption whose validity is external to the derivation chain; the algebraic dependencies noted in the skeptic attack affect correctness of the model but do not create a definitional loop or statistical forcing inside the paper's equations. The reference to Parts I and II is only for the final CDPR reduction and does not underpin the distance limit itself. The derivation is therefore self-contained as a conditional proof.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard algebraic number theory facts about cyclotomic fields and log embeddings together with lattice geometry; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math The logarithmic embedding maps the unit group of Q(ζ_{2^k}) to a full-rank lattice in R^{n} with the usual Euclidean structure.
    Invoked to define the log-unit lattice and the CVP distance.
  • domain assumption Short ring elements have sub-Gaussian coordinates under the canonical embedding.
    Used to obtain the L^∞ bound O(√log n) and the L² limit.

pith-pipeline@v0.9.0 · 5738 in / 1642 out tokens · 36524 ms · 2026-05-19T22:55:40.783553+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

41 extracted references · 41 canonical work pages

  1. [1]

    Recovering short generators of principal ideals in cyclotomic rings

    Ronald Cramer, L´ eo Ducas, Chris Peikert, and Oded Regev. Recovering short generators of principal ideals in cyclotomic rings. InAdvances in Cryptology-EUROCRYPT 2016, volume 9666 ofLecture Notes in Computer Science, pp.559-585. Springer, 2016

    work page 2016

  2. [2]

    Short stickelberger class relations and application to Ideal-SVP

    Ronald Cramer, L´ eo Ducas, and Benjamin Wesolowski. Short stickelberger class relations and application to Ideal-SVP. InAdvances in Cryptology-EUROCRYPT 2017, volume 10210 ofLecture Notes in Computer Science, pp.324-348. Springer, 2017

    work page 2017

  3. [3]

    Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time.Journal of the ACM, 68: 1-26, 2021

    Ronald Cramer, L´ eo Ducas, and Benjamin Wesolowski. Mildly short vectors in cyclotomic ideal lattices in quantum polynomial time.Journal of the ACM, 68: 1-26, 2021

    work page 2021

  4. [4]

    Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields

    Jean-Fran¸ cois Biasse and Fang Song. Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields. InPro- ceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.893-902. SIAM, 2016

    work page 2016

  5. [5]

    Approx-SVP in ideal lattices with pre-processing

    Alice Pellet-Mary, Guillaume Hanrot, and Damien Stehl´ e. Approx-SVP in ideal lattices with pre-processing. InAdvances in Cryptology-EUROCRYPT 2019, volume 11477 ofLecture Notes in Computer Science, pp.685-716. Springer, 2019

    work page 2019

  6. [6]

    Ideal-SVP is hard for small-norm uniform prime ideals

    Jo¨ el Felderhoff, Alice Pellet-Mary, Damien Stehl´ e, and Benjamin Wesolowski. Ideal-SVP is hard for small-norm uniform prime ideals. InTheory of Cryptography Conference 2023, volume 14372 ofLecture Notes in Computer Science, pp.324-348. Springer, 2023

    work page 2023

  7. [7]

    Worst-case to average-case reductions for module lattices.Designs, Codes and Cryptography, 75: 565-599, 2015

    Adeline Langlois and Damien Stehl´ e. Worst-case to average-case reductions for module lattices.Designs, Codes and Cryptography, 75: 565-599, 2015

    work page 2015

  8. [8]

    Cryptanalysis of rank-2 module-lip in totally real number fields

    Guilhem Mureau, Alice Pellet-Mary, Georgii Pliatsok, and Alexandre Wallet. Cryptanalysis of rank-2 module-lip in totally real number fields. InAdvances in Cryptology-EUROCRYPT 2024, pp.226-255. Springer, 2024. 24

    work page 2024

  9. [9]

    Cryptanalysis of rank-2 module- lip: A single real embedding is all it takes

    Bill Allombert, Alice Pellet-Mary, and Wessel van Woerden. Cryptanalysis of rank-2 module- lip: A single real embedding is all it takes. InAdvances in Cryptology-EUROCRYPT 2025, volume 15602 ofLecture Notes in Computer Science, pp.184-212. Springer, 2025

    work page 2025

  10. [10]

    A reduction from Hawk to the principal ideal problem in a quaternion algebra

    Cl´ emence 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. InAdvances in Cryptology-EUROCRYPT 2025, volume 15602 of Lecture Notes in Computer Science, pp.154-183. Springer, 2025

    work page 2025

  11. [11]

    Predicting module-lattice reduction

    L´ eo 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

    work page 2025

  12. [12]

    On Lovasz lattice reduction and the nearest lattice point problem.Combina- torica, 6: 1-13, 1986

    Laszlo Babai. On Lovasz lattice reduction and the nearest lattice point problem.Combina- torica, 6: 1-13, 1986

    work page 1986

  13. [13]

    Lenstra, Hendrik W

    Arjen K. Lenstra, Hendrik W. Lenstra, and Laszlo Lovasz. Factoring polynomials with rational coefficients.Mathematische Annalen, 261: 515-534, 1982

    work page 1982

  14. [14]

    A hierarchy of polynomial time lattice basis reduction algorithms

    Claus-Peter Schnorr. A hierarchy of polynomial time lattice basis reduction algorithms. Theoretical Computer Science, 53: 201-224, 1987

    work page 1987

  15. [15]

    Nicolas Gama and Phong Q. Nguyen. Finding short lattice vectors within Mordell’s inequality. InProceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp.207-216. ACM, 2008

    work page 2008

  16. [16]

    Solving the shortest vector problem in 2 n time using discrete Gaussian sampling

    Divesh Aggarwal, Daniel Dadush, Oded Regev, and Noah Stephens-Davidowitz. Solving the shortest vector problem in 2 n time using discrete Gaussian sampling. InProceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), pp.733-742. ACM, 2015

    work page 2015

  17. [17]

    Wiley, 3rd edition, 1995

    Patrick Billingsley.Probability and Measure. Wiley, 3rd edition, 1995

    work page 1995

  18. [18]

    William Feller.An Introduction to Probability Theory and Its Applications, volume 2, Wiley, 2nd edition, 1971

    work page 1971

  19. [19]

    Cambridge University Press, 2018

    Roman Vershynin.High-Dimensional Probability: An Introduction with Applications in Data Science. Cambridge University Press, 2018

    work page 2018

  20. [20]

    Oxford University Press, 2013

    St´ ephane Boucheron, G´ abor Lugosi, and Pascal Massart.Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013

    work page 2013

  21. [21]

    American Mathematical Society, 2012

    Terence Tao.Topics in Random Matrix Theory. American Mathematical Society, 2012

    work page 2012

  22. [22]

    Stegun.Handbook of Mathematical Functions

    Milton Abramowitz and Irene A. Stegun.Handbook of Mathematical Functions. Dover, 1964

    work page 1964

  23. [23]

    Springer, 1999

    J¨ urgen Neukirch.Algebraic Number Theory, volume 322 ofGrundlehren der mathematischen Wissenschaften. Springer, 1999

    work page 1999

  24. [24]

    On the Stickelberger ideal and the circular units of a cyclotomic field

    Warren Sinnott. On the Stickelberger ideal and the circular units of a cyclotomic field. Annals of Mathematics, 108: 107-134, 1978

    work page 1978

  25. [25]

    Washington.Introduction to Cyclotomic Fields, volume 83, Graduate Texts in Mathematics

    Lawrence C. Washington.Introduction to Cyclotomic Fields, volume 83, Graduate Texts in Mathematics. Springer, 2nd edition, 1997

    work page 1997

  26. [26]

    Cambridge University Press, 5th edition, 2019

    Rick Durrett.Probability: Theory and Examples. Cambridge University Press, 5th edition, 2019. 25

    work page 2019

  27. [27]

    Some theorems on distribution functions.Journal of the London Mathematical Society, s1-11: 290-294, 1936

    Harald Cram´ er and Herman Wold. Some theorems on distribution functions.Journal of the London Mathematical Society, s1-11: 290-294, 1936

    work page 1936

  28. [28]

    Wiley, New York, 2nd edition, 1999

    Patrick Billingsley.Convergence of Probability Measures. Wiley, New York, 2nd edition, 1999

    work page 1999

  29. [29]

    Petrov.Limit Theorems of Probability Theory

    Valentin V. Petrov.Limit Theorems of Probability Theory. Oxford University Press, 1995

    work page 1995

  30. [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

    work page 1941

  31. [31]

    On the Liapounoff limit of error in the theory of probability.Arkiv f¨ or matematik, astronomi och fysik, 28A(9):1–19, 1942

    Carl-Gustav Esseen. On the Liapounoff limit of error in the theory of probability.Arkiv f¨ or matematik, astronomi och fysik, 28A(9):1–19, 1942

    work page 1942

  32. [32]

    Whittaker and George N

    Edmund T. Whittaker and George N. Watson.A Course of Modern Analysis. Cambridge University Press, 1996

    work page 1996

  33. [33]

    5.15 (Polygamma Functions)

    https://dlmf.nist.gov/.Release 1.1.12, 2023; Chapter 5 (Gamma Function), Sec. 5.15 (Polygamma Functions)

    work page 2023

  34. [34]

    Sur les fonctions ind´ ependantes.Fundamenta Mathematicae, 29: 60-90, 1937

    J´ ozef Marcinkiewicz and Antoni Zygmund. Sur les fonctions ind´ ependantes.Fundamenta Mathematicae, 29: 60-90, 1937

    work page 1937

  35. [35]

    de la Pe na and Evarist Gin´ e.Decoupling: From Dependence to Independence

    Victor H. de la Pe na and Evarist Gin´ e.Decoupling: From Dependence to Independence. Springer, New York, 1999

    work page 1999

  36. [36]

    On the method of bounded differences

    Colin McDiarmid. On the method of bounded differences. In J. Siemons, editor,Surveys in Combinatorics 1989, volume 141 ofLondon Mathematical Society Lecture Note Series, pp.148-188. Cambridge University Press, 1989

    work page 1989

  37. [37]

    M. R. Leadbetter, Georg Lindgren, and Holger Rootz´ en.Extremes and Related Properties of Random Sequences and Processes. Springer, New York, 1983

    work page 1983

  38. [38]

    Simeon M. Berman. Limit theorems for the maximum term in stationary sequences.Annals of Mathematical Statistics, 35: 502-516, 1964

    work page 1964

  39. [39]

    Wainwright.High-Dimensional Statistics: A Non-Asymptotic Viewpoint

    Martin J. Wainwright.High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cam- bridge University Press, 2019

    work page 2019

  40. [40]

    Muirhead.Aspects of Multivariate Statistical Theory

    Robb J. Muirhead.Aspects of Multivariate Statistical Theory. Wiley, New York, 1982

    work page 1982

  41. [41]

    Forrester.Log-Gases and Random Matrices

    Peter J. Forrester.Log-Gases and Random Matrices. Princeton University Press, 2010. 26

    work page 2010