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.15858

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

Ming-Xing Luo

cs.CRquant-phSubmitted Apr 17, 2026• Announced Apr 20, 2026• Revised May 7, 2026 (v2)
v1 · Apr 17, 2026v2 · May 7, 2026
arXivHTMLPDF

Abstract

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.

Comments
24 pages

Related papers

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

cs.CRCross-listedarXiv:2604.22900•Apr 27, 2026•0 citations

A Decade of Lattice Cryptography

Chris Peikert

Lattice-based cryptography is the use of conjectured hard problems on point lattices in Rn as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under worst-case intractability assumptions, and solutions to long-standing open problems in cryptography. This monograph surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution (SIS) and learning with errors (LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.

now publishers, Inc. eBooks•Jan 1, 2016•269 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

A Decade of Lattice Cryptography

Chris Peikert

Lattice-based cryptography is the use of conjectured hard problems on point lattices in ℝn as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under worst-case intractability assumptions, and solutions to long-standing open problems in cryptography. This work surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution (SIS) and learning with errors (LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.

Foundations and Trends® in Theoretical Computer Science•Mar 24, 2016•597 citations

Quantum-Secure Primitives from Ideal Lattices: Beyond Factoring for Asymmetric Cryptography

Revista, Zen, MATH, 10

The advent of quantum computing poses a significant threat to the security foundations of current asymmetric cryptographic schemes, which primarily rely on the perceived difficulty of integer factorization and discrete logarithm problems. Shor's algorithm, in particular, demonstrates that a sufficiently powerful quantum computer could break these schemes efficiently, necessitating the development of quantum-resistant alternatives. This paper explores the construction of quantum-secure primitives utilizing ideal lattices, a specialized class of lattices that offer enhanced efficiency and structural advantages compared to general lattices. We delve into the theoretical underpinnings of ideal lattices, including the Ring Learning With Errors (Ring-LWE) problem and the NTRU problem, which are believed to be hard even for quantum computers. The paper reviews the evolution of lattice-based cryptography, analyzes the security reductions from worst-case lattice problems to average-case problem instances relevant for cryptographic constructions, and discusses the practical implications for key encapsulation mechanisms and digital signatures. We examine the current state of ideal lattice-based schemes, such as those standardized by NIST, and consider their performance characteristics, key sizes, and resistance to known attacks, including side-channel vulnerabilities. Our analysis highlights that ideal lattices provide a robust and efficient foundation for building the next generation of asymmetric cryptographic primitives, moving beyond the vulnerabilities inherent in factoring-based systems.

•Dec 3, 2025•0 citations
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.
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.
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.
Lattice-based cryptography is the use of conjectured hard problems on point lattices in Rn as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under worst-case intractability assumptions, and solutions to long-standing open problems in cryptography. This monograph surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution (SIS) and learning with errors (LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.
Lattice-based cryptography is the use of conjectured hard problems on point lattices in ℝn as the foundation for secure cryptographic systems. Attractive features of lattice cryptography include apparent resistance to quantum attacks (in contrast with most number-theoretic cryptography), high asymptotic efficiency and parallelism, security under worst-case intractability assumptions, and solutions to long-standing open problems in cryptography. This work surveys most of the major developments in lattice cryptography over the past ten years. The main focus is on the foundational short integer solution (SIS) and learning with errors (LWE) problems (and their more efficient ring-based variants), their provable hardness assuming the worst-case intractability of standard lattice problems, and their many cryptographic applications.
The advent of quantum computing poses a significant threat to the security foundations of current asymmetric cryptographic schemes, which primarily rely on the perceived difficulty of integer factorization and discrete logarithm problems. Shor's algorithm, in particular, demonstrates that a sufficiently powerful quantum computer could break these schemes efficiently, necessitating the development of quantum-resistant alternatives. This paper explores the construction of quantum-secure primitives utilizing ideal lattices, a specialized class of lattices that offer enhanced efficiency and structural advantages compared to general lattices. We delve into the theoretical underpinnings of ideal lattices, including the Ring Learning With Errors (Ring-LWE) problem and the NTRU problem, which are believed to be hard even for quantum computers. The paper reviews the evolution of lattice-based cryptography, analyzes the security reductions from worst-case lattice problems to average-case problem instances relevant for cryptographic constructions, and discusses the practical implications for key encapsulation mechanisms and digital signatures. We examine the current state of ideal lattice-based schemes, such as those standardized by NIST, and consider their performance characteristics, key sizes, and resistance to known attacks, including side-channel vulnerabilities. Our analysis highlights that ideal lattices provide a robust and efficient foundation for building the next generation of asymmetric cryptographic primitives, moving beyond the vulnerabilities inherent in factoring-based systems.