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

• URL: http://arxiv.org/abs/2605.17404v1
• Date: Sun, 17 May 2026 12:00:59 GMT
• Title: Module Lattice Security (Part III): Structured CVP Distance on the Log-Unit Lattice
• Abstract summary: We show that the $L2$ CVP distance from a random short ring element to the log-unit lattice converges to $frac2sqrt6sqrtn$ as $n=2k-1toinfty$.<n>For the $Linfty$ norm, the maximum over $n$ sub-Gaussian coordinates yields $O(sqrtlog n)$ which translates into a sub-polynomial approximation factor for the Short Generator Problem.
• Score: 1.0152838128195467
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We prove that the $L^2$ CVP distance from a random short ring element to the log-unit lattice of $\Q(ζ_{2^k})$ converges to $\fracπ{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 $σ_{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.

Related papers

• Zero-SNR Analyticity of the Scalar MMSE Is Equivalent to Gaussianity [0.7499255435598924]
  We prove that the minimum mean-square error $operatornamemmse_X(s)$ is analytic at zero signal-to-noise ratio if and only if $X$ is Gaussian.<n>A zero of $mgeq 2$ splits according to the roots of a Hermitemath and instead contributes a prefactor $n-m/2er_msqrt2n$.
  arXiv  Detail & Related papers  (2026-09-14T05:07:20Z)
• SIC dimension towers via cyclotomic polynomials [0.0]
  We prove a structure for the dimension towers$d_k(D)_kgeq0$ which arise in the number-theoretic formulation of Zauner's SIC-POVM conjecture.
  arXiv  Detail & Related papers  (2026-09-03T19:51:19Z)
• SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules [17.893655677334575]
  We prove that the decision version of the Shortest Vector Problem ($mathrmSVP$) in the $ell binary$-norm is $mathrmNP$-complete on full-rank free sub-counts.<n>The construction also gives $mathrmNP$-hardness of search-$mathrmSVP$ under matrix-time Turing reductions.
  arXiv  Detail & Related papers  (2026-09-01T16:04:35Z)
• Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting [0.9023847175654603]
  We prove $c_mathrmF(T_n),c_2(T_n)=(log(n+1)3/2)$ with no sign, sparsity, or squareness restriction.<n>Within the pure-$varepsilon$-DP matrix-mechanism class, the optimized maximum and mean squared errors are both $(varepsilon-2log3(n+1))$.
  arXiv  Detail & Related papers  (2026-07-30T14:41:34Z)
• Optimal Scalar Quantization for Matrix Multiplication: Closed-Form Density and Phase Transition [50.36362492608702]
  We study entrywise scalar quantization of two matrices prior to multiplication.<n>We obtain a closed-form optimal point density [ star(u) propto exp!left(-fracu26right)bigl( (1-2)+2u22bigr), qquad u=fracx_X,, and prove a correlation-driven phase transition.
  arXiv  Detail & Related papers  (2026-03-20T01:53:44Z)
• Rényi exponent landscape of multipartite entanglement in free-fermion systems [51.56484100374058]
  We show that the Rényi tripartite information $I_3() exhibits a qualitatively $exclusion-dependent scaling at small Fermi momentum.<n>A direct consequence is a replica obstruction: $I_m(n)/I_m(1) sim zm-1 to 0$ for all integer $n geq 2$, so the leading von Neumann signal cannot be reconstructed from integer Rényi data.
  arXiv  Detail & Related papers  (2026-03-09T22:27:00Z)
• Tripartite information of free fermions: a universal entanglement coefficient from the sine kernel [51.56484100374058]
  We study the tripartite information I_3 of free fermions on two-dimensional lattices partitioned into three adjacent strips of width w.<n>We find that g(z) has a unique zero at z* = 1.329 +/- 0.001: modes with k_F w z* violate monogamy of mutual information.<n>Two exact cancellations -- of the z ln z area-law terms and of the z2 terms -- are intrinsic to the I_3 combination.
  arXiv  Detail & Related papers  (2026-03-03T15:39:35Z)
• Computational Hardness of Private Coreset [84.99100741615423]
  For a given input set of points, a coreset is another set of points such that the $k$-means objective for any candidate solution is preserved up to a multiplicative $(, 1/n(1))$ factor (and some additive factor)<n>We show that no-time $(, 1/n(1))$-DP algorithm can compute a coreset for $k$-means in the $ell_infty$-metric for some constant $> 0$ (and some constant additive factor)<n>For $k$-means in the
  arXiv  Detail & Related papers  (2026-02-19T15:58:49Z)
• Permanents of matrix ensembles: computation, distribution, and geometry [0.0]
  We use the GPU to greaatly accelerate the computation of permanents over $mathbbC,$ $mathbbR,$ $mathbbF_p$ and $mathbbQ.$<n>We study the permanent along geodesics on the unitary group.<n>For the geodesic from the identity to the $n$-cycle permutation matrix, we find a universal scaling function $f(t)=frac1nln|perm((t))|$ that is independent of$n$ in
  arXiv  Detail & Related papers  (2026-02-08T22:31:42Z)
• On the Intrinsic Dimensions of Data in Kernel Learning [1.675218291152252]
  We show that for kernels such as the Laplace kernel, the effective dimension $d_K$ can be significantly smaller than the Minkowski dimension $d_$ provably holds on regular domains.<n>Our results show that, for kernels such as the Laplace kernel, the effective dimension $d_K$ can be significantly smaller than the Minkowski dimension $d_$ provably holds on regular domains.
  arXiv  Detail & Related papers  (2026-01-22T17:32:24Z)
• The Algorithmic Phase Transition in Symmetric Correlated Spiked Wigner Model [0.0]
  We study the computational task of detecting and estimating correlated signals in a pair of spiked Wigner matrices.<n>An algorithm can leverage the correlation between the spikes to detect and estimate the signals even in regimes where efficiently recovering either $x$ from $X$ alone or $y$ from $Y$ alone is believed to be computationally infeasible.
  arXiv  Detail & Related papers  (2025-11-08T15:23:44Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.