arXiv:2605.17404

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

Ming-Xing Luo

cs.DScs.CRmath.NTmath.STquant-phSubmitted May 17, 2026• Announced May 19, 2026

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.

Comments: 26 pages (simplied version). Most important part in this series

Related papers

Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection

Ming-Xing Luo

cs.CRCross-listedarXiv:2604.22900Apr 27, 20260 citations

Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Ming-Xing Luo

quant-pharXiv:2605.17412May 19, 20260 citations

Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for $k \le 12$

Ming-Xing Luo

cs.CRCross-listedarXiv:2604.15858Apr 20, 2026

Hardness of Structured Lattices Problems for Post-Quantum Cryptography

Felderhoff, Joël

Nov 26, 20240 citations

Qubo model for the Closest Vector Problem

Eduardo Canale, Claudio Qureshi, Alfredo Viola

arXiv:2304.03616Apr 7, 20231 citation

Worst-Case to Average-Case Reductions for Module Lattices.

Adeline Roux-Langlois, Damien Stehlé

Jan 1, 20128 citations

arXiv:2605.17404

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

Ming-Xing Luo

cs.DScs.CRmath.NTmath.STquant-phSubmitted May 17, 2026• Announced May 19, 2026

arXiv HTML PDF

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}

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.

Comments: 26 pages (simplied version). Most important part in this series

Related papers

Module Lattice Security (Part II): Module Lattice Reduction via Optimal Sign Selection

Ming-Xing Luo

We extend the CDPR's quantum attack from ideal lattices to module lattices over $2^k$ -th cyclotomic rings. Using trace orthogonality of the power basis, we decompose a rank- $d$ module into mutually orthogonal rank- $1$ submodules, and apply CDPR's analysis to each independently and return the shortest candidate. The Hermite factor $\exp(\tilde{O}(\sqrt{n}))$ matches the ideal case, with a module reduction factor $α_d=O(1)$ independent of the rank, under a balance hypothesis (proved for Gaussian distribution) automatic for MLWE-distributed bases. To enable a bounded-precision implementation, we replace coordinate-wise rounding with Chinese Remainder Theorem-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding radius from $n/2$ to $\le 1$ at cost $O(d^2 r n \log n)$ . Finally, we reformulate the CDPR's sign-selection step as a mixed-integer linear program and prove its optimum is no more than 1/2 for all $k$ ( $\approx 0.4407$ for all tested $k\le 12$ , conjecturally universal). This replaces the previous heuristic discrepancy $Θ(\sqrt{nk})$ . All results build on the class number condition $h_k^+=1$ established in Part I of this series.We extend the CDPR's quantum attack from ideal lattices to module lattices over $2^k$-th cyclotomic rings. Using trace orthogonality of the power basis, we decompose a rank-$d$ module into mutually orthogonal rank-$1$ submodules, and apply CDPR's analysis to each independently and return the shortest candidate. The Hermite factor $\exp(\tilde{O}(\sqrt{n}))$ matches the ideal case, with a module reduction factor $α_d=O(1)$ independent of the rank, under a balance hypothesis (proved for Gaussian distribution) automatic for MLWE-distributed bases. To enable a bounded-precision implementation, we replace coordinate-wise rounding with Chinese Remainder Theorem-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding radius from $n/2$ to $\le 1$ at cost $O(d^2 r n \log n)$. Finally, we reformulate the CDPR's sign-selection step as a mixed-integer linear program and prove its optimum is no more than 1/2 for all $k$ ($\approx 0.4407$ for all tested $k\le 12$, conjecturally universal). This replaces the previous heuristic discrepancy $Θ(\sqrt{nk})$. All results build on the class number condition $h_k^+=1$ established in Part I of this series.

cs.CRCross-listedarXiv:2604.22900Apr 27, 20260 citations

Module Lattice Security (Part IV): Probabilistic Polynomial Quantum Attack on Module-LWE over 2-Power Cyclotomics

Ming-Xing Luo

We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies $γ\le 21 < q/2=1664.5$ for ML-KEM-1024, with a success probability $\ge 0.99$ . We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(ζ_8)\subset\cdots\subset \Q(ζ_{2^k})$ which yields a polynomial-time quantum algorithm costing $O(n^3 \log^2 n)$ gates, $O(n^2 \log n)$ qubits, and poly $(n)$ classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies $γ\le 21 < q/2=1664.5$ for ML-KEM-1024, with a success probability $\ge 0.99$. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(ζ_8)\subset\cdots\subset \Q(ζ_{2^k})$ which yields a polynomial-time quantum algorithm costing $O(n^3 \log^2 n)$ gates, $O(n^2 \log n)$ qubits, and poly$(n)$ classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.

quant-pharXiv:2605.17412May 19, 20260 citations

Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for $k \le 12$ Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for $k \le 12$

Ming-Xing Luo

Weber's conjecture (1886) governs three aspects of lattice-based cryptography: the solvability of the Principal Ideal Problem, the freeness of modules over rings of integers, and the tightness of worst-case-to-average-case reductions in Ring-LWE (R-LWE) and Module-LWE (MLWE). Existing verifications for $k \ge 9$ rely on Generalized Riemann Hypothesis (GRH). In this paper, we present the first unconditional proof for $k \le 12$ . Our method combines the Fukuda-Komatsu computational sieve, inductive structure of the cyclotomic $\mathbb{Z}_2$ -tower, and Herbrand's theorem.Weber's conjecture (1886) governs three aspects of lattice-based cryptography: the solvability of the Principal Ideal Problem, the freeness of modules over rings of integers, and the tightness of worst-case-to-average-case reductions in Ring-LWE (R-LWE) and Module-LWE (MLWE). Existing verifications for $k \ge 9$ rely on Generalized Riemann Hypothesis (GRH). In this paper, we present the first unconditional proof for $k \le 12$. Our method combines the Fukuda-Komatsu computational sieve, inductive structure of the cyclotomic $\mathbb{Z}_2$-tower, and Herbrand's theorem.

cs.CRCross-listedarXiv:2604.15858Apr 20, 2026

Hardness of Structured Lattices Problems for Post-Quantum Cryptography

Felderhoff, Joël

The security of cryptographic protocols is based on the presumed difficulty of algorithmic problems. Among those identified so far, some of the best problems to serve as a foundation for quantum-proof cryptography come from lattices. Lattices are a mathematical structure defined as a set of space vectors generated by integer combinations of a finite number of linearly independent real vectors (its basis). A typical example of a related security problem is the Shortest Vector Problem (SVP). Given a base of an n-dimensional lattice, find a non-zero short vector. For efficiency reasons, these problems are restricted to lattices arising from number theory, known as structured lattices. As the security assumptions for these particular lattices are different from those for unstructured lattices, it is necessary to study them specifically, which is the aim of this thesis.We have studied the case of NTRU and uSVP modules in rank 2, proving that the SVP problem is equivalent on these two families of lattices. We also show a worst-case to average-case reduction for rank-2 uSVP lattices. Then we show that solving SVP on a prime ideal of small norm is no easier than solving SVP on any ideal.The security of cryptographic protocols is based on the presumed difficulty of algorithmic problems. Among those identified so far, some of the best problems to serve as a foundation for quantum-proof cryptography come from lattices. Lattices are a mathematical structure defined as a set of space vectors generated by integer combinations of a finite number of linearly independent real vectors (its basis). A typical example of a related security problem is the Shortest Vector Problem (SVP). Given a base of an n-dimensional lattice, find a non-zero short vector. For efficiency reasons, these problems are restricted to lattices arising from number theory, known as structured lattices. As the security assumptions for these particular lattices are different from those for unstructured lattices, it is necessary to study them specifically, which is the aim of this thesis.We have studied the case of NTRU and uSVP modules in rank 2, proving that the SVP problem is equivalent on these two families of lattices. We also show a worst-case to average-case reduction for rank-2 uSVP lattices. Then we show that solving SVP on a prime ideal of small norm is no easier than solving SVP on any ideal.

Nov 26, 20240 citations

Qubo model for the Closest Vector Problem

Eduardo Canale, Claudio Qureshi, Alfredo Viola

In this paper we consider the closest vector problem (CVP) for lattices $Λ\subseteq \mathbb{Z}^n$ given by a generator matrix $A\in \mathcal{M}_{n\times n}(\mathbb{Z})$ . Let $b>0$ be the maximum of the absolute values of the entries of the matrix $A$ . We prove that the CVP can be reduced in polynomial time to a quadratic unconstrained binary optimization (QUBO) problem in $O(n^2(\log(n)+\log(b)))$ binary variables, where the length of the coefficients in the corresponding quadratic form is $O(n(\log(n)+\log(b)))$ .In this paper we consider the closest vector problem (CVP) for lattices $Λ\subseteq \mathbb{Z}^n$ given by a generator matrix $A\in \mathcal{M}_{n\times n}(\mathbb{Z})$. Let $b>0$ be the maximum of the absolute values of the entries of the matrix $A$. We prove that the CVP can be reduced in polynomial time to a quadratic unconstrained binary optimization (QUBO) problem in $O(n^2(\log(n)+\log(b)))$ binary variables, where the length of the coefficients in the corresponding quadratic form is $O(n(\log(n)+\log(b)))$.

arXiv:2304.03616Apr 7, 20231 citation

Worst-Case to Average-Case Reductions for Module Lattices.

Adeline Roux-Langlois, Damien Stehlé

Abstract. Most lattice-based cryptographic schemes are built upon the assumed hardness of the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. Their efficiencies can be drastically improved by switching the hardness assumptions to the more compact Ring-SIS and Ring-LWE problems. However, this change of hardness assumptions comes along with a possible security weakening: SIS and LWE are known to be at least as hard as standard (worst-case) problems on euclidean lattices, whereas Ring-SIS and Ring-LWE are only known to be as hard as their restrictions to special classes of ideal lattices, corresponding to ideals of some polynomial rings. In this work, we define the Module-SIS and Module-LWE problems, which bridge SIS with Ring-SIS, and LWE with Ring-LWE, respectively. We prove that these average-case problems are at least as hard as standard lattice problems restricted to module lattices (which themselves generalize arbitrary and ideal lattices). As these new problems enlarge the toolbox of the lattice-based cryptographer, they could prove useful for designing new schemes. Importantly, the worst-case to average-case reductions for the module problems are (qualitatively) sharp, in the sense that there exist converse reductions. This property is not known to hold in the context of Ring-SIS/Ring-LWE: Ideal lattice problems could reveal easy without impacting the hardness of Ring-SIS/Ring-LWE. 1Abstract. Most lattice-based cryptographic schemes are built upon the assumed hardness of the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. Their efficiencies can be drastically improved by switching the hardness assumptions to the more compact Ring-SIS and Ring-LWE problems. However, this change of hardness assumptions comes along with a possible security weakening: SIS and LWE are known to be at least as hard as standard (worst-case) problems on euclidean lattices, whereas Ring-SIS and Ring-LWE are only known to be as hard as their restrictions to special classes of ideal lattices, corresponding to ideals of some polynomial rings. In this work, we define the Module-SIS and Module-LWE problems, which bridge SIS with Ring-SIS, and LWE with Ring-LWE, respectively. We prove that these average-case problems are at least as hard as standard lattice problems restricted to module lattices (which themselves generalize arbitrary and ideal lattices). As these new problems enlarge the toolbox of the lattice-based cryptographer, they could prove useful for designing new schemes. Importantly, the worst-case to average-case reductions for the module problems are (qualitatively) sharp, in the sense that there exist converse reductions. This property is not known to hold in the context of Ring-SIS/Ring-LWE: Ideal lattice problems could reveal easy without impacting the hardness of Ring-SIS/Ring-LWE. 1

Jan 1, 20128 citations

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}

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})

σ_{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.

We extend the CDPR's quantum attack from ideal lattices to module lattices over

2^k

-th cyclotomic rings. Using trace orthogonality of the power basis, we decompose a rank-

d

module into mutually orthogonal rank-

1

submodules, and apply CDPR's analysis to each independently and return the shortest candidate. The Hermite factor

\exp(\tilde{O}(\sqrt{n}))

matches the ideal case, with a module reduction factor

α_d=O(1)

independent of the rank, under a balance hypothesis (proved for Gaussian distribution) automatic for MLWE-distributed bases. To enable a bounded-precision implementation, we replace coordinate-wise rounding with Chinese Remainder Theorem-scaled rounding at totally split primes, reducing the Gram-Schmidt rounding radius from

n/2

\le 1

at cost

O(d^2 r n \log n)

. Finally, we reformulate the CDPR's sign-selection step as a mixed-integer linear program and prove its optimum is no more than 1/2 for all

k

(

\approx 0.4407

for all tested

k\le 12

, conjecturally universal). This replaces the previous heuristic discrepancy

Θ(\sqrt{nk})

. All results build on the class number condition

h_k^+=1

established in Part I of this series.

We present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies

γ\le 21 < q/2=1664.5

for ML-KEM-1024, with a success probability

\ge 0.99

. We apply a tower decomposition of the Principal Ideal Problem (PIP) through the chain $\Q\subset \Q(ζ_8)\subset\cdots\subset \Q(ζ_{2^k})$ which yields a polynomial-time quantum algorithm costing

O(n^3 \log^2 n)

gates,

O(n^2 \log n)

qubits, and poly

(n)

classical bit operations. We extend the analysis to Falcon, Hawk, and NTRU over 2-power cyclotomic rings with polynomial-time quantum algorithms.

Module Lattice Security (Part I): Unconditional Verification of Weber's Conjecture for

k \le 12

k \ge 9

rely on Generalized Riemann Hypothesis (GRH). In this paper, we present the first unconditional proof for

k \le 12

. Our method combines the Fukuda-Komatsu computational sieve, inductive structure of the cyclotomic

\mathbb{Z}_2

-tower, and Herbrand's theorem.

In this paper we consider the closest vector problem (CVP) for lattices

Λ\subseteq \mathbb{Z}^n

given by a generator matrix

A\in \mathcal{M}_{n\times n}(\mathbb{Z})

. Let

b>0

be the maximum of the absolute values of the entries of the matrix

A

. We prove that the CVP can be reduced in polynomial time to a quadratic unconstrained binary optimization (QUBO) problem in

O(n^2(\log(n)+\log(b)))

binary variables, where the length of the coefficients in the corresponding quadratic form is

O(n(\log(n)+\log(b)))