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: Fine-Grained Parameter Selection without Compromising Performance

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•1 citation

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

CRT-Decomposed ΣΣΣ-Protocols for CSIDH

I. Dey, I. Cherkaoui

We construct a zero-knowledge proof of knowledge for the CSIDH group action that exploits the Chinese Remainder Theorem (CRT) structure of the ideal class group, available whenever the group structure is known exactly, as for CSIDH-512. We prove perfect completeness, perfect special honest-verifier zero-knowledge, and 2-special soundness, in which the secret is recovered from two accepting transcripts by one subtraction and one modular inversion per CRT component; no rewinding loop, lattice reduction, or heuristic sampling appears in the extractor. Because each round admits exactly two responses, Unruh's transform yields a non-interactive proof with straight-line extraction in the quantum random oracle model (QROM), removing the multiplicative forking-lemma loss. We instantiate the scheme on the CSIDH-512 class group, verify the algebraic layer by machine over the exact 258-bit modulus ($10^4$ random instances, all passing), and report protocol-level simulations in the exponent model: Monte Carlo soundness rates matching the proven $2^{-t}$ bound within 95\% confidence at every tested $t$, serialized signature sizes within 1.6\% of the formulas, instrumented action counts, and a scaled meet-in-the-middle attack whose measured cost follows the predicted $\sqrt{q}$ law. We further prove two delimiting results: CRT decomposition cannot enlarge the per-round challenge space, and publishing the CRT hop curves lowers classical key-recovery cost from about $2^{128.6}$ to about $2^{67.3}$ group action evaluations. The construction is therefore correct and structurally complete today, but quantitatively secure only on future parameters whose class number has large prime factors. We compare against CSI-FiSh, CSI-Otter, and Tanuki; a tightly secure blind signature from this proof of knowledge is left to future work.

cs.CRCross-listedarXiv:2609.26258•Aug 14, 2026
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.
We construct a zero-knowledge proof of knowledge for the CSIDH group action that exploits the Chinese Remainder Theorem (CRT) structure of the ideal class group, available whenever the group structure is known exactly, as for CSIDH-512. We prove perfect completeness, perfect special honest-verifier zero-knowledge, and 2-special soundness, in which the secret is recovered from two accepting transcripts by one subtraction and one modular inversion per CRT component; no rewinding loop, lattice reduction, or heuristic sampling appears in the extractor. Because each round admits exactly two responses, Unruh's transform yields a non-interactive proof with straight-line extraction in the quantum random oracle model (QROM), removing the multiplicative forking-lemma loss. We instantiate the scheme on the CSIDH-512 class group, verify the algebraic layer by machine over the exact 258-bit modulus (10410^4104 random instances, all passing), and report protocol-level simulations in the exponent model: Monte Carlo soundness rates matching the proven 2−t2^{-t}2−t bound within 95\% confidence at every tested ttt, serialized signature sizes within 1.6\% of the formulas, instrumented action counts, and a scaled meet-in-the-middle attack whose measured cost follows the predicted q\sqrt{q}q​ law. We further prove two delimiting results: CRT decomposition cannot enlarge the per-round challenge space, and publishing the CRT hop curves lowers classical key-recovery cost from about 2128.62^{128.6}2128.6 to about 267.32^{67.3}267.3 group action evaluations. The construction is therefore correct and structurally complete today, but quantitatively secure only on future parameters whose class number has large prime factors. We compare against CSI-FiSh, CSI-Otter, and Tanuki; a tightly secure blind signature from this proof of knowledge is left to future work.