⚛️ quantum physics

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

This paper presents the first unconditional proof verifying Weber's conjecture for $k \le 12$ by combining the Fukuda-Komatsu computational sieve, the inductive structure of the cyclotomic $\mathbb{Z}_2$ -tower, and Herbrand's theorem, thereby eliminating the reliance on the Generalized Riemann Hypothesis required for previous results with $k \ge 9$ .

Original authors: Ming-Xing Luo

Published 2026-04-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Ming-Xing Luo

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a fortress to protect your digital secrets from future super-computers (quantum computers). To do this, you need to build your fortress out of very specific, incredibly strong mathematical bricks called lattices.

For the last 15 years, cryptographers have been using a special type of brick made from "cyclotomic fields" (a fancy name for a specific kind of number system). These bricks are great because they are small, fast to process, and theoretically unbreakable.

However, there was a tiny, nagging doubt in the foundation of these bricks. It was a 138-year-old question called Weber's Conjecture.

The Problem: The "Ghost" in the Machine

Think of your number system as a massive library. In a perfect library, every book (number) can be uniquely identified by its author and title. But in some complex libraries, books get lost, or multiple copies of the same book exist in different sections, making it impossible to find the "original" one.

In math terms, this is called the Class Number.

If the Class Number is 1, the library is perfect. Every book has a unique, principal identity. The system is clean.
If the Class Number is greater than 1, there are "ghosts" (hidden complexities). The system is messy.

For decades, mathematicians knew that for small libraries (up to a certain size), the Class Number was 1. But for the larger libraries used in modern encryption (sizes 9 through 12), they could only prove it was 1 if they assumed a massive, unproven hypothesis called the Generalized Riemann Hypothesis (GRH).

The Analogy: It's like saying, "This bridge is safe to cross, provided that gravity works exactly as we think it does." We are 99.9% sure gravity works, but we wanted to prove the bridge is safe without that assumption.

The Solution: A Three-Stage Detective Story

Ming-Xing Luo, a mathematician from Southwest Jiaotong University, has finally solved this. He didn't just check the bridge; he proved it's safe using a three-step detective process that requires no "ifs" or "buts."

Here is how he did it, using simple analogies:

Stage 1: The "Small Fish" Net (The Sieve)

First, the detective needs to know what kind of "monsters" (prime numbers) could possibly be hiding in the library.

The Logic: He used a clever filter (the Fukuda-Komatsu sieve) to check all small monsters.
The Result: He proved that any monster small enough to be easily caught (less than 1 billion) is definitely not there.
The Catch: This left only "giant" monsters. But he also proved a rule: If a giant monster exists, it must wear a very specific, rare costume (it must satisfy a strict mathematical congruence). This immediately eliminated 99.9% of the universe of possible monsters.

Stage 2: The "Tower" Climb (Inductive Logic)

The libraries in question are stacked like a tower. The library for size 9 sits on top of size 8, size 10 on top of 9, and so on.

The Logic: We already knew the bottom floor (size 8) was perfect (Class Number = 1).
The Trick: Luo showed that if the floor below is perfect, the floor above can only have "ghosts" in very specific, high-up rooms (called eigenspaces). It's like saying, "If the basement is clean, any mess on the 10th floor can only be in the attic, not in the living room."
The Result: This pruned the search space massively. We no longer had to check the whole library; we only had to check the "attic" of the largest rooms.

Stage 3: The "Magic Number" Check (Herbrand's Theorem)

Now, the detective had a very short list of potential "giant monsters" that could hide in the "attic."

The Logic: He used a powerful mathematical theorem (Herbrand's theorem) which says: "If a monster exists, it must divide a specific, pre-calculated number (a Bernoulli number)."
The Result: He calculated these numbers. They were huge (up to 143 digits long), but manageable for modern computers. He factored them and checked if any of the "giant monsters" from Stage 1 were hiding inside.
The Verdict: Nothing was found. The list of potential monsters was empty.

The Big Picture: Why This Matters

1. The Fortress is Solid:
The encryption standards chosen by the US government (NIST) for the post-quantum era (like ML-KEM and ML-DSA) rely on these number systems. For years, security proofs said, "This is secure, assuming the Generalized Riemann Hypothesis is true."
Now, we can say: "This is secure, period." The foundation is unconditional.

2. No More "What Ifs":
In cryptography, we don't like "what ifs." If a future mathematician disproves the Generalized Riemann Hypothesis, it could theoretically shake the foundations of these encryption methods. By removing that dependency, Luo has made the security of our future digital world much more robust.

3. The "Ghost" is Gone:
The paper confirms that for all the sizes of libraries currently used in real-world encryption, the "Class Number" is exactly 1. The libraries are perfect. Every book has a unique key. The math works exactly as the cryptographers hoped it would.

Summary

Think of this paper as a master locksmith who, instead of just saying "This lock is probably unbreakable," actually took the lock apart, examined every single gear, and proved mathematically that no key exists that can open it without the correct code.

We now know, with 100% certainty, that the mathematical bricks used to build our future quantum-proof internet are solid, clean, and free of hidden ghosts.

1. Problem Statement

The paper addresses Weber's Conjecture (1886), a fundamental open problem in algebraic number theory with critical implications for post-quantum cryptography.

The Conjecture: For every integer $k \ge 1$ , the maximal real subfield $K_k^+ = \mathbb{Q}(\zeta_{2^k} + \zeta_{2^k}^{-1})$ of the $2^k$ -th cyclotomic field has a class number $h_k^+ = 1$ .
Cryptographic Relevance: Modern lattice-based standards (NIST's ML-KEM, ML-DSA) rely on rings of integers of these fields ( $\mathbb{Z}[x]/(x^{2^k}+1)$ $Z [x] / (x^{2^{k}} + 1)$ ).
- Module Freeness: If $h_k^+ = 1$ , every finitely generated torsion-free module over the ring of integers is free. This is a prerequisite for the security proofs of Module-LWE (MLWE) based schemes.
- Ideal Structure: If $h_k^+ = 1$ , the Principal Ideal Problem (PIP) becomes trivial (all ideals are principal), simplifying the reduction from worst-case to average-case lattice problems.
Current State: Prior to this work, the conjecture was verified unconditionally only for $k \le 8$ . For $9 \le k \le 12$ , existing proofs relied on the Generalized Riemann Hypothesis (GRH) to bound the Minkowski bound, making the verification conditional.

2. Methodology

The author presents a novel, unconditional proof for $k \le 12$ by combining three distinct mathematical techniques to reduce the search space of potential prime divisors of the class number to a computationally finite set.

Stage 1: Small-Prime Elimination (Fukuda-Komatsu Sieve)

Technique: Uses the Wieferich criterion applied to cyclotomic units.
Mechanism: The paper verifies computationally that for all primes $\ell < 10^9$ , the Wieferich condition holds.
Result: This eliminates all small primes as potential divisors of $h_k^+$ . Furthermore, it establishes that any remaining prime divisor $\ell$ must satisfy the strong congruence condition:
$\ell \equiv \pm 1 \pmod{2^{k-1}}$
This drastically reduces the density of candidate primes (e.g., for $k=10$ , only 1 in 256 primes near $10^9$ are candidates).

Stage 2: Eigenspace Pruning (Norm-Coherence Argument)

Technique: Exploits the inductive structure of the Cyclotomic $\mathbb{Z}_2$ -tower ( $K_8^+ \subset K_9^+ \subset \dots \subset K_{12}^+$ ) and Galois representation theory.
Mechanism:
- The class group $\text{Cl}(K_k^+)[\ell]$ is decomposed into eigenspaces based on the Galois group $G_k \cong \mathbb{Z}/2^{k-2}\mathbb{Z}$ .
- Using the fact that $h_8^+ = 1$ (proven unconditionally by Miller) and the norm map properties in the tower, the author proves inductively that for $k > 8$ , any non-trivial $\ell$ -torsion must reside only in the eigenspaces corresponding to full-order characters (characters of order $2^{k-2}$ ).
- All lower-order eigenspaces are proven to be trivial.
Result: The problem is reduced from checking all characters to checking only the full-order characters.

Stage 3: Finite Bounding (Herbrand's Theorem)

Technique: Applies Herbrand's Theorem (and the Herbrand-Ribet theorem) to link the non-vanishing of class group eigenspaces to the divisibility of Generalized Bernoulli numbers.
Mechanism:
- If a prime $\ell$ divides $h_k^+$ , it must divide the norm of a specific generalized Bernoulli number $B_{1, \psi}$ associated with a full-order character.
- The paper derives tight second-moment bounds for these Bernoulli norms. For $k=10$ , the bound is reduced from a worst-case $10^{309}$ to a manageable $10^{143}$ digits.
Result: This creates a finite, computable set $S_k$ $S_{k}$ of candidate primes. The verification then reduces to:
1. Factoring the bounded Bernoulli norm integer.
2. Filtering factors using the congruence $\ell \equiv \pm 1 \pmod{2^{k-1}}$ .
3. Running the Wieferich test (Stage 1) on the remaining candidates.

3. Key Contributions

First Unconditional Proof: Provides the first proof of Weber's conjecture for $9 \le k \le 12$ without relying on GRH.
Algorithmic Efficiency:
- Utilizes Galois orbit symmetry to show that all conjugate pairs of full-order characters yield the same Bernoulli norm. This reduces the factorization task from $n/4$ integers to a single integer per $k$ .
- For $k=10$ , the integer to factor has at most 143 decimal digits, which is tractable using the Elliptic Curve Method (ECM).
- For $k=12$ , the bound is $\approx 726$ digits, accessible via a combination of ECM and the Number Field Sieve (NFS).
Inductive Framework: Establishes a rigorous inductive step from $k-1$ to $k$ using the $\mathbb{Z}_2$ -tower structure, eliminating the need for independent verification of each layer.

4. Results

Theorem: For all $k \in \{9, 10, 11, 12\}$ , the class number of the maximal real subfield is $h_k^+ = 1$ .
Verification: The computational verification involves factoring a single integer of $\le 143$ digits (for $k=10$ ) and performing a small number of modular exponentiations. The paper confirms that no primes satisfy the necessary conditions to divide $h_k^+$ .
Table 1 Update: The paper updates the historical record (Table 1 in the text), marking $k \le 12$ as "GRH-free" (Yes), whereas previous results for $k \ge 9$ were marked "Conditional."

5. Significance

Cryptographic Security: The result solidifies the theoretical foundation of NIST's post-quantum standards (ML-KEM, ML-DSA).
- It confirms that the Module-LWE security reductions, which assume the underlying module is free, hold unconditionally for the parameters used in these standards.
- It validates the noise analysis and correctness proofs that rely on the ring of integers having class number 1.
Quantum Resilience: While $h_k^+ = 1$ implies the Principal Ideal Problem (PIP) is trivial (potentially vulnerable to quantum attacks like those by Biasse and Song), the paper clarifies that Module-LWE (used in standards) is distinct from Ideal-LWE. The security of ML-KEM/ML-DSA relies on the hardness of the Module-SVP/Module-LWE, which remains robust even if $h_k^+ = 1$ .
Methodological Advance: The combination of computational sieving, Iwasawa-theoretic tower induction, and analytic bounds on Bernoulli numbers offers a blueprint for resolving similar class number conjectures in other families of totally real fields.

In summary, this paper removes a major theoretical uncertainty in lattice-based cryptography by proving that the algebraic structures underpinning current post-quantum standards behave as expected (class number 1) without needing unproven hypotheses.