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

1. Problématique et Contexte

Conjecture de Weber (1886) :
La conjecture stipule que pour tout entier $k \ge 1$, le sous-corps réel maximal $K_k^+ = \mathbb{Q}(\zeta_{2^k} + \zeta_{2^k}^{-1})$ du corps cyclotomique $2^k$-ième possède un nombre de classes $h_k^+ = 1$. Autrement dit, l'anneau d'entiers $\mathcal{O}_{K_k^+}$ est un domaine à factorisation unique (UFD) pour les idéaux.

Importance pour la Cryptographie Post-Quantique :
La résolution de cette conjecture est cruciale pour la sécurité des schémas cryptographiques basés sur les réseaux (Lattice-based cryptography), notamment les standards NIST finalisés en 2024 (ML-KEM, ML-DSA, FN-DSA) qui reposent sur des anneaux de polynômes cyclotomiques $\mathbb{Z}[x]/(x^{2^k}+1)$.
La conjecture affecte trois aspects fondamentaux :

1. Problème de l'Idéal Principal (PIP) : Si $h_k^+ = 1$, tout idéal est principal. Cela pourrait permettre à des algorithmes quantiques de résoudre le PIP en temps polynomial, réduisant la sécurité au problème du générateur court (SGP).
2. Liberté des Modules : Sur un domaine de Dedekind, un module de type fini sans torsion est libre si et seulement si sa classe de Steinitz est triviale. Si $h_k^+ = 1$, tous les modules sur $\mathcal{O}_{K_k^+}$ sont libres, une hypothèse clé dans les preuves de sécurité de ML-KEM et ML-DSA.
3. Réductions de Complexité : La réduction du pire cas au cas moyen pour Ring-LWE (R-LWE) et Module-LWE (ML-LWE) est plus serrée et rigoureuse lorsque le nombre de classes est 1.

État de l'art :
Avant cet article, la conjecture était vérifiée de manière inconditionnelle (sans hypothèse non prouvée) uniquement pour $k \le 8$. Pour $9 \le k \le 12$, les vérifications existantes dépendaient de l'Hypothèse de Riemann Généralisée (GRH), principalement en raison de la croissance exponentielle de la borne de Minkowski qui rend le crible direct impossible sans GRH.

2. Méthodologie

L'auteur propose une preuve inconditionnelle pour $k \le 12$ en combinant trois étapes séquentielles qui réduisent l'ensemble des candidats potentiels pour diviser $h_k^+$ à un ensemble fini et calculable.

Étape 1 : Élimination des petits nombres premiers (Crible de Fukuda-Komatsu)

• Principe : Utilisation du critère de Wieferich appliqué aux unités cyclotomiques.
• Mécanisme : Pour tout nombre premier impair $\ell < 10^9$, on vérifie si $\ell$ peut diviser $h_k^+$. Si l'unité cyclotomique $\xi_5$ ne satisfait pas une condition de congruence spécifique (liée à l'ordre de $\xi_5$ modulo les idéaux au-dessus de $\ell$), alors $\ell \nmid h_k^+$.
• Résultat intermédiaire : On établit que tout diviseur premier $\ell$ de $h_k^+$ doit satisfaire la condition de congruence forte $\ell \equiv \pm 1 \pmod{2^{k-1}}$. Cela élimine la quasi-totalité des petits nombres premiers.

Étape 2 : Élagage des sous-espaces propres (Argument de cohérence de norme)

• Structure : Exploitation de la structure de tour cyclotomique $\mathbb{Z}_2$ ($K_8^+ \subset K_9^+ \subset \dots \subset K_{12}^+$) et de la décomposition par sous-espaces propres du groupe de classes sous l'action du groupe de Galois.
• Induction : En partant de la base connue $h_8^+ = 1$ (prouvée par Miller), l'article démontre par récurrence que pour $k \in \{9, 10, 11, 12\}$, toute torsion $\ell$-aire non triviale dans le groupe de classes ne peut résider que dans les sous-espaces propres correspondant aux caractères d'ordre plein (full-order characters) du groupe de Galois.
• Conséquence : Cela élimine tous les caractères d'ordre inférieur, réduisant drastiquement le nombre de conditions à vérifier.

Étape 3 : Bornage fini (Théorème de Herbrand)

• Lien arithmétique : Application du théorème de Herbrand (et de Ribet) qui relie la non-vanishing d'un sous-espace propre du groupe de classes à la divisibilité d'un nombre de Bernoulli généralisé $B_{1,\psi}$ par $\ell$.
• Calcul : Pour chaque caractère d'ordre plein restant, on calcule la norme du nombre de Bernoulli généralisé associé.
• Filtrage : L'ensemble des candidats $S_k$ est constitué des facteurs premiers de ces normes qui satisfont les conditions de congruence de l'étape 1.
• Complexité : Grâce à des bornes de moments (second moment bound), les normes à factoriser sont limitées à des entiers d'environ 143 chiffres décimaux pour $k=10$ (et jusqu'à ~325 pour $k=11$), ce qui est traitable par des méthodes modernes comme la méthode des courbes elliptiques (ECM) ou le crible de corps de nombres (NFS).

3. Contributions Clés

1. Preuve Inconditionnelle : Première démonstration mathématique rigoureuse que $h_k^+ = 1$ pour $k \le 12$ sans aucune hypothèse non prouvée (comme la GRH).
2. Algorithme de Vérification : Présentation d'un algorithme complet (Algorithme 1) qui transforme un problème théorique infini en un problème de factorisation d'entiers fini et gérable.
3. Optimisation par Symétrie : Démonstration que toutes les paires de caractères conjugués d'ordre plein donnent la même norme, réduisant le nombre de factorisations nécessaires d'un facteur $n/4$ à 1 par couche de la tour.
4. Analyse de Complexité : Estimation précise du temps de calcul nécessaire (de quelques minutes à quelques semaines selon $k$) en utilisant des méthodes de factorisation modernes (ECM, NFS).

4. Résultats

• Théorème Principal : Pour tout $k \in \{9, 10, 11, 12\}$, le nombre de classes du sous-corps réel maximal $K_k^+$ est égal à 1 ($h_k^+ = 1$).
• Validation : L'ensemble des candidats $S_k$ pour chaque $k$ a été vérifié. Aucun nombre premier ne satisfait simultanément les conditions de congruence, de divisibilité des normes de Bernoulli et de critère de Wieferich.
• Données Techniques :
  • Pour $k=10$ (utilisé dans ML-KEM/ML-DSA), la borne maximale de la norme est d'environ $10^{143}$.
  • La factorisation de ces entiers est réalisable en quelques heures avec ECM.
  • Pour $k=11$ et $12$, la complexité augmente mais reste dans le domaine du calculable (jours/semaines).

5. Signification et Implications

• Sécurité Cryptographique : Ce résultat valide les hypothèses sous-jacentes aux preuves de sécurité des standards NIST (ML-KEM, ML-DSA). Il confirme que les modules sur les anneaux d'entiers de ces corps sont libres, ce qui est essentiel pour la réduction du pire cas au cas moyen et l'absence de biais structurels dans la génération de clés.
• Résilience aux Attaques Quantiques : Bien que $h_k^+ = 1$ simplifie le PIP (rendant les schémas basés uniquement sur les idéaux vulnérables aux attaques quantiques de type Biasse-Song), les standards NIST utilisent le problème ML-LWE (Module-LWE). L'article confirme que la structure libre des modules garantit que les réductions de sécurité restent valides et que les attaques connues sur les réseaux idéaux ne compromettent pas directement la sécurité de ML-KEM/ML-DSA.
• Avancée Théorique : L'article résout un problème ouvert majeur de la théorie des nombres (conjecture de Weber) pour une plage de paramètres critique, en combinant de manière innovante la théorie d'Iwasawa, la théorie des caractères et le calcul numérique.
• Perspectives : La méthode développée ouvre la voie à la vérification de conjectures similaires pour d'autres familles de corps totalement réels, bien que l'extension aux puissances de nombres premiers impairs ($p$-adic) nécessite des adaptations de la tour $\mathbb{Z}_2$ vers une tour $\mathbb{Z}_p$.

En résumé, cet article fournit une fondation mathématique solide et inconditionnelle pour la sécurité des cryptosystèmes post-quantiques basés sur les réseaux, éliminant le besoin de supposer l'Hypothèse de Riemann Généralisée pour les paramètres standards actuels.