Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.22900

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

Ming-Xing Luo

cs.CRcs.ITquant-phSubmitted Apr 24, 2026• Announced Apr 27, 2026• 0 citations• Revised Jun 2, 2026 (v2)
v1 · Apr 24, 2026v2 · Jun 2, 2026
arXivHTMLPDF

Abstract

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.

Comments
30 pages, add new results and proofs of previous simulations and examples. The key change is alpha_d=sqrt C which is changed into 1.3346.This does not affect all the polynomical algorithms in Part IV. For simulation video see the comment of Part IV in this series

Related papers

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

Ming-Xing Luo

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.

cs.DSCross-listedarXiv:2605.17404•May 19, 2026

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.

quant-pharXiv:2605.17412•May 19, 2026•0 citations

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.

cs.CRCross-listedarXiv:2604.15858•Apr 20, 2026

Structured Module Lattice-based Cryptography

Joppe W. Bos, Joost Renes, Fréderik Vercauteren +1 more

The ongoing transition to Post-Quantum Cryptography (PQC) has highlighted the need for cryptographic schemes that offer high security, strong performance, and fine-grained parameter selection. In lattice-based cryptography, particularly for the popular module variants of learning with errors (Module-LWE) and learning with rounding (Module-LWR) schemes based on power-of-two cyclotomics, existing constructions often force parameter choices that either overshoot or undershoot desired security levels due to structural constraints. In this work, we introduce a new class of techniques that are the advantages of both worlds: structured Module-LWE (or LWR) embeds more algebraic structure than a module such that it significantly improves performance, yet less structure than a power-of-two cyclotomic ring such that it still enables more flexible and efficient parameter selection. We present two concrete instances: a construction based on a radical extension of a two-power cyclotomic field denoted radical Ring-LWE (RR-LWE) or Ring-LWR (RR-LWR), and a cyclotomic block-ring module lattice approach (BRM-LWE or BRM-LWR). These new structured Module-LWE and LWR reduce the required number of uniformly random bytes in its matrix by a factor up to the module rank and allow efficient NTT implementations while enabling more granular security-performance trade-offs. We analyze the security of these constructions, provide practical parameter sets, and present implementation results demonstrating a performance improvement of up to 37% compared to an optimized implementation of ML-KEM. Our techniques apply to both key encapsulation mechanisms and digital signature schemes, offering a pathway to more adaptable and performant PQC standards.

IACR Transactions on Cryptographic Hardware and Embedded Systems•Jul 17, 2026•0 citations

Shortest Vector Problems in Ideal Lattices and the Hardness of Ring Learning with Errors

Zen Revista, 10 MFC

A rigorous derivation of quantum reductions for ideal lattice constraints within the module-theoretic framework of cyclotomic number fields and the asymptotic hardness of algebraic lattice problems.

•Jan 4, 2026•0 citations

Hardness of the Shortest Vector Problem on Ideal Lattices under Quantum Reductions

Zen Revista, 10 MFC

The security of efficient post-quantum cryptographic primitives, particularly those based on the Ring Learning With Errors (Ring-LWE) problem, relies fundamentally on the presumed intractability of the Shortest Vector Problem (SVP) over ideal lattices. This monograph investigates the hardness of Ideal-SVP in the presence of quantum adversaries. We rigorously analyze the worst-case to average-case reductions that underpin the security of ideal lattice-based schemes, extending classical Gaussian smoothing arguments to the quantum setting. Specifically, we examine the impact of quantum sieving algorithms and the Quantum Fourier Transform (QFT) on the algebraic structure of number fields. While quantum algorithms provide a quadratic speedup for general lattice sieving, we argue that the additional algebraic structure of ideal lattices does not yield a catastrophic collapse in hardness under current quantum reduction models. We present a synthesis of recent results concerning the lower bounds of quantum query complexity for Ideal-SVP, establishing that for cyclotomic fields of degree n, the problem remains hard up to sub-exponential factors, thereby validating the asymptotic security of structured lattice cryptography.

•Feb 4, 2026•0 citations
We extend the CDPR's quantum attack from ideal lattices to module lattices over 2k2^k2k-th cyclotomic rings. Using trace orthogonality of the power basis, we decompose a rank-ddd module into mutually orthogonal rank-111 submodules, and apply CDPR's analysis to each independently and return the shortest candidate. The Hermite factor exp⁡(O~(n))\exp(\tilde{O}(\sqrt{n}))exp(O~(n​)) matches the ideal case, with a module reduction factor αd=O(1)α_d=O(1)α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/2n/2n/2 to ≤1\le 1≤1 at cost O(d2rnlog⁡n)O(d^2 r n \log n)O(d2rnlogn). 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 kkk (≈0.4407\approx 0.4407≈0.4407 for all tested k≤12k\le 12k≤12, conjecturally universal). This replaces the previous heuristic discrepancy Θ(nk)Θ(\sqrt{nk})Θ(nk​). All results build on the class number condition hk+=1h_k^+=1hk+​=1 established in Part I of this series.
We prove that the L2L^2L2 CVP distance from a random short ring element to the log-unit lattice of $\Q(ζ_{2^k})$ converges to π26n\fracπ{2\sqrt{6}}\sqrt{n}26​π​n​ as n=2k−1→∞n=2^{k-1}\to\inftyn=2k−1→∞. We then show that this target lies inside the Voronoi cell of the origin for k≥4k\ge 4k≥4. For the L∞L^\inftyL∞ norm, the maximum over nnn sub-Gaussian coordinates yields O(log⁡n)O(\sqrt{\log n})O(logn​) 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)σ_{g_0}=O(1)σg0​​=O(1) independent of the modulus qqq. 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 present a quantum attack on ML-KEM and related 2-power cyclotomic lattice schemes. Combining with Parts I-III, we provide an algorithm and verify the resulting approximation factor satisfies γ≤21<q/2=1664.5γ\le 21 < q/2=1664.5γ≤21<q/2=1664.5 for ML-KEM-1024, with a success probability ≥0.99\ge 0.99≥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(n3log⁡2n)O(n^3 \log^2 n)O(n3log2n) gates, O(n2log⁡n)O(n^2 \log n)O(n2logn) qubits, and poly(n)(n)(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≤12k \le 12k≤12
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≥9k \ge 9k≥9 rely on Generalized Riemann Hypothesis (GRH). In this paper, we present the first unconditional proof for k≤12k \le 12k≤12. Our method combines the Fukuda-Komatsu computational sieve, inductive structure of the cyclotomic Z2\mathbb{Z}_2Z2​-tower, and Herbrand's theorem.
The ongoing transition to Post-Quantum Cryptography (PQC) has highlighted the need for cryptographic schemes that offer high security, strong performance, and fine-grained parameter selection. In lattice-based cryptography, particularly for the popular module variants of learning with errors (Module-LWE) and learning with rounding (Module-LWR) schemes based on power-of-two cyclotomics, existing constructions often force parameter choices that either overshoot or undershoot desired security levels due to structural constraints. In this work, we introduce a new class of techniques that are the advantages of both worlds: structured Module-LWE (or LWR) embeds more algebraic structure than a module such that it significantly improves performance, yet less structure than a power-of-two cyclotomic ring such that it still enables more flexible and efficient parameter selection. We present two concrete instances: a construction based on a radical extension of a two-power cyclotomic field denoted radical Ring-LWE (RR-LWE) or Ring-LWR (RR-LWR), and a cyclotomic block-ring module lattice approach (BRM-LWE or BRM-LWR). These new structured Module-LWE and LWR reduce the required number of uniformly random bytes in its matrix by a factor up to the module rank and allow efficient NTT implementations while enabling more granular security-performance trade-offs. We analyze the security of these constructions, provide practical parameter sets, and present implementation results demonstrating a performance improvement of up to 37% compared to an optimized implementation of ML-KEM. Our techniques apply to both key encapsulation mechanisms and digital signature schemes, offering a pathway to more adaptable and performant PQC standards.
The security of efficient post-quantum cryptographic primitives, particularly those based on the Ring Learning With Errors (Ring-LWE) problem, relies fundamentally on the presumed intractability of the Shortest Vector Problem (SVP) over ideal lattices. This monograph investigates the hardness of Ideal-SVP in the presence of quantum adversaries. We rigorously analyze the worst-case to average-case reductions that underpin the security of ideal lattice-based schemes, extending classical Gaussian smoothing arguments to the quantum setting. Specifically, we examine the impact of quantum sieving algorithms and the Quantum Fourier Transform (QFT) on the algebraic structure of number fields. While quantum algorithms provide a quadratic speedup for general lattice sieving, we argue that the additional algebraic structure of ideal lattices does not yield a catastrophic collapse in hardness under current quantum reduction models. We present a synthesis of recent results concerning the lower bounds of quantum query complexity for Ideal-SVP, establishing that for cyclotomic fields of degree n, the problem remains hard up to sub-exponential factors, thereby validating the asymptotic security of structured lattice cryptography.