Primitive-Root Determinant Densities over Prime Fields and Implications for PRIM-LWE

Cet article résout de manière inconditionnelle une question ouverte sur le problème PRIM-LWE en établissant que la densité des matrices à déterminant racine primitive sur les corps finis est strictement positive, en prouvant que son minimum sur les premiers $p \le x$ décroît comme $1/\log\log x$ et en fournissant des bornes explicites garantissant une faible surcharge d'échantillonnage pour les moduli cryptographiques standardisés.

L'essentiel

Voici une explication de ce document technique, traduite en langage simple et imagé, comme si nous discutions autour d'un café.

🌟 Le Titre : La "Clé Primitive" et les Serrures Mathématiques

Imaginez que vous êtes un architecte de sécurité informatique. Vous construisez des coffres-forts numériques (des systèmes de cryptographie) pour protéger les données. Pour cela, vous utilisez des "serrures" mathématiques basées sur des nombres premiers (des nombres indivisibles comme 2, 3, 5, 7...).

Dans un nouveau type de serrure appelé PRIM-LWE, il y a une règle très spécifique : la clé qui ouvre la serrure (un nombre appelé le "déterminant") doit être une "racine primitive".

L'analogie de la clé :
Imaginez que votre serrure a des milliers de positions possibles. Une "racine primitive" est une clé magique qui, si vous la tournez, visite toutes les positions possibles avant de revenir au début. C'est la clé la plus efficace, celle qui explore tout le système.

Le problème, c'est que toutes les serrures ne sont pas égales. Certaines serrures (certaines valeurs de nombres premiers) sont très difficiles à équiper de cette clé magique. La question que se posait l'auteur, Vipin Singh Sehrawat, était la suivante :

"Est-il possible de trouver une serrure si mal conçue qu'il devient presque impossible de trouver une telle clé ?"

🔍 La Réponse : "Oui, mais c'est très lent"

L'auteur répond OUI, mais avec une nuance importante.

1. Le problème des serrures "mauvaises" :
   Il existe une infinité de serrures (nombres premiers) où la probabilité de trouver une clé primitive est extrêmement faible. Si vous choisissez une serrure au hasard parmi les pires, vous devrez essayer des millions de clés avant d'en trouver une qui fonctionne.

   • En langage mathématique : La densité de ces clés tend vers zéro.

2. La vitesse de la chute :
   Cependant, cette chute vers zéro est extrêmement lente. C'est comme si vous descendiez une colline, mais une colline si douce que vous mettez des siècles à atteindre le bas.

   • L'auteur prouve que même pour les pires serrures, la probabilité de succès ne tombe pas à zéro instantanément. Elle diminue très doucement, comme l'inverse du logarithme du logarithme du nombre (une fonction qui grandit si lentement qu'elle en est presque plate).

🛠️ Pourquoi cela compte-t-il pour la sécurité ?

Dans le monde de la cryptographie (comme les standards NIST que vous utilisez peut-être pour sécuriser vos emails ou vos transactions), on utilise des nombres premiers spécifiques pour faire fonctionner les algorithmes rapidement.

L'auteur a fait un travail de détective pour vérifier si ces nombres premiers standards (utilisés par le gouvernement américain et les banques) tombaient dans le piège des "mauvaises serrures".

Les bonnes nouvelles :

• Les serrures standards sont solides : Les nombres premiers utilisés dans les standards actuels (comme ceux pour ML-KEM et ML-DSA) ont une structure "propre". Leurs facteurs (les petits nombres qui les composent) sont bien contrôlés.
• Le coût est faible : Pour ces serrures standards, la probabilité de trouver une clé primitive est bonne. En pratique, si vous essayez de générer une clé, vous n'aurez besoin que de 2 à 4 essais en moyenne pour réussir. C'est négligeable pour un ordinateur.
• Le danger théorique : Le seul danger serait de choisir exprès une serrure bizarre (un nombre premier très spécial avec une structure de facteurs très complexe). Mais personne ne le ferait par erreur.

🎨 L'Analogie Finale : Le Parc d'Attractions

Imaginez un immense parc d'attractions avec des millions de manèges (les nombres premiers).

• La plupart des manèges sont bien conçus : vous pouvez facilement trouver un ticket valide (la clé primitive).
• Il existe une théorie selon laquelle certains manèges, très rares et très complexes, auraient des tickets si rares qu'il faudrait fouiller des années pour en trouver un.
• La découverte de l'auteur : Il a prouvé mathématiquement que ces manèges "impossibles" existent bien.
• Mais : Il a aussi montré que les manèges que nous utilisons réellement (les standards NIST) sont des manèges bien entretenus, où l'on trouve des tickets très facilement.

📝 En Résumé

1. Le problème : On voulait savoir si la sécurité d'un nouveau système cryptographique (PRIM-LWE) pouvait s'effondrer si l'on choisissait un mauvais nombre premier.
2. La preuve : Oui, mathématiquement, on peut trouver des nombres premiers où la sécurité est théoriquement très faible (la probabilité de succès est proche de zéro).
3. La réalité : Cette faiblesse est si rare et si lente à apparaître que pour tous les nombres premiers utilisés dans la vraie vie (cryptographie bancaire, internet sécurisé), le système est parfaitement sûr. Le "coût" pour trouver une clé est minime (quelques essais).
4. La conclusion : Pas de panique ! Les ingénieurs peuvent continuer à utiliser les standards actuels en toute confiance. L'auteur a juste cartographié les zones de danger théorique pour s'assurer que nous ne nous y aventurons pas par erreur.

C'est une victoire de la rigueur mathématique : on a prouvé qu'un risque théorique existe, mais qu'il est totalement maîtrisé dans la pratique.

Résumé technique

1. Contexte et Problématique

Le problème PRIM-LWE (Learning with Errors avec déterminant à racine primitive) est une variante du problème LWE standard, introduite par Sehrawat, Yeo et Desmedt. Dans cette variante, la matrice secrète $S$ utilisée dans la réduction de décision LWE vers décision PRIM-LWE doit avoir un déterminant qui est une racine primitive du corps fini $\mathbb{F}_p$ (c'est-à-dire que $\det(S)$ génère le groupe multiplicatif $\mathbb{F}_p^*$).

La sécurité et l'efficacité de la réduction dépendent de la densité des matrices ayant cette propriété. Soit $c_n(p)$ la fraction exacte des matrices $n \times n$ sur $\mathbb{F}_p$ dont le déterminant est une racine primitive. La constante de réduction uniforme en dimension est définie comme :
$$c(p) := \inf_{m \ge 1} c_m(p) = \lim_{m \to \infty} c_m(p) = \frac{\phi(p-1)}{p-1} \prod_{j=1}^{\infty} \left(1 - \frac{1}{p^j}\right)$$
où $\phi$ est l'indicatrice d'Euler.

La question ouverte : Sehrawat, Yeo et Desmedt se sont demandé si $\inf_{p \text{ premier}} c(p) = 0$. Ils ont observé que si l'on suppose l'infinitude des nombres premiers factoriels (de la forme $p = \prod_{i=1}^k p_i + 1$), alors $c(p)$ tendrait vers 0. Cependant, l'infinitude de ces nombres premiers est une conjecture non résolue. La question centrale était de savoir si ce résultat pouvait être prouvé inconditionnellement.

2. Méthodologie

L'auteur résout ce problème en utilisant uniquement des outils classiques de la théorie analytique des nombres, sans faire appel à des conjectures non prouvées :

1. Théorème de Dirichlet sur les nombres premiers en progression arithmétique : Pour tout entier $k$, il existe une infinité de nombres premiers $p$ tels que $p \equiv 1 \pmod{N_k}$, où $N_k$ est le $k$-ième nombre primoriel ($N_k = \prod_{i=1}^k p_i$).
2. Formule du produit de Mertens : Elle permet d'estimer le comportement asymptotique du produit $\prod_{q \le x} (1 - 1/q) \sim \frac{e^{-\gamma}}{\log x}$.
3. Théorème de Linnik : Il fournit une borne supérieure sur le plus petit nombre premier dans une progression arithmétique ($p(a, q) \le C_0 q^L$), ce qui est crucial pour quantifier la vitesse de décroissance.
4. Théorie des fonctions additives (Erdős–Wintner) : Utilisée pour analyser la distribution limite de la quantité $\phi(p-1)/(p-1)$ sur les nombres premiers.

3. Résultats Clés et Contributions

A. Preuve Inconditionnelle de la Nullité de l'Infimum

L'article prouve que $\inf_{p} c(p) = 0$ de manière inconditionnelle.

• Mécanisme : Pour tout $k$, on choisit un nombre premier $p \equiv 1 \pmod{N_k}$. Alors $N_k$ divise $p-1$. Le rapport $\frac{\phi(p-1)}{p-1}$ est donc majoré par $\prod_{i=1}^k (1 - 1/p_i)$.
• Par le théorème de Mertens, ce produit tend vers 0 lorsque $k \to \infty$.
• Cela contredit l'hypothèse selon laquelle il faudrait des nombres premiers factoriels spécifiques ; il suffit d'une infinité de nombres premiers dans certaines progressions arithmétiques (garantie par Dirichlet).

B. Ordre de Grandeur de la Décroissance

L'auteur établit l'ordre de grandeur précis du minimum de $c(p)$ pour $p \le x$ :
$$\min_{p \le x} c(p) \asymp \frac{1}{\log \log x}$$

• La décroissance vers zéro est extrêmement lente (double logarithmique).
• Pour des tailles de clés cryptographiques réalistes (ex: $2^{128}$ou$2^{4096}$),$\log \log x$ reste petit (environ 4,5 à 7,95), ce qui signifie que la densité ne s'effondre pas rapidement, mais que le pire cas théorique existe.

C. Distribution Limite Singulière

Le papier démontre que la quantité $c(p)$ possède une distribution limite continue et purement singulière sur l'intervalle $[0, 1/2]$.

• La fonction de répartition $G(\tau)$ est strictement croissante sur $[0, 1/2]$.
• Le support de la distribution est exactement $[0, 1/2]$.
• Cela implique que pour tout $\tau \in (0, 1/2)$, il existe une densité relative positive de nombres premiers pour lesquels $c(p) \le \tau$, et une autre pour lesquels $c(p) > \tau$.

D. Bornes Inférieures Explicites pour la Cryptographie

L'article fournit des bornes inférieures explicites pour $c(q)$ basées sur le nombre de facteurs premiers distincts de $q-1$, noté $\omega(q-1)$.

• Théorème 8 : $c(q) \ge P_3 \prod_{i=1}^{\omega(q-1)} (1 - 1/p_i)$, où $P_3 \approx 0.56$.
• Application aux moduli NIST :
  • Pour ML-KEM ($q = 3329$) : $c(q) \approx 0.4614$, ce qui donne un surcoût d'échantillonnage de rejet d'environ 2.17.
  • Pour ML-DSA ($q = 8380417$) : $c(q) \approx 0.2933$, ce qui donne un surcoût d'environ 3.42.
• Ces valeurs sont faibles et constantes, confirmant que les moduli standards actuels sont sûrs et efficaces pour PRIM-LWE.
• Une borne universelle simple est donnée pour $q > 2^{30}$ : $1/c(q) \le 1.79 \log q$.

4. Signification et Implications

1. Résolution d'une question ouverte : La preuve inconditionnelle que l'infimum est nul ferme le débat théorique sur la possibilité d'une densité arbitrairement faible, sans dépendre de conjectures non prouvées sur les nombres premiers factoriels.
2. Impact sur la sécurité de PRIM-LWE :
   • Bien que le surcoût d'échantillonnage ($1/c(p)$) puisse théoriquement croître comme$\Omega(\log \log p)$ pour une sous-suite de nombres premiers mal choisis, cette croissance est très lente.
   • Pour les moduli utilisés en pratique (notamment ceux compatibles avec la Transformée Numérique de Théorie des Nombres, ou NTT), la structure de factorisation de $q-1$ est contrôlée (peu de petits facteurs premiers impairs).
   • Par conséquent, le surcoût reste borné par une petite constante pour les paramètres cryptographiques standards.
3. Nuance sur la compatibilité NTT : L'article clarifie que la simple compatibilité NTT ($q \equiv 1 \pmod{2^t}$) ne garantit pas une bonne borne inférieure sur $c(q)$. C'est la structure de factorisation globale de $q-1$ (en particulier le nombre de facteurs premiers impairs) qui détermine la densité. Heureusement, les moduli standards satisfont cette condition.
4. Conclusion pratique : Les résultats ne révèlent aucune faiblesse structurelle pratique dans PRIM-LWE. La réduction de décision LWE vers décision PRIM-LWE reste valide avec un facteur de perte constant et faible pour les moduli cryptographiques courants.

En résumé, ce papier affine notre compréhension théorique de la densité des déterminants à racine primitive, prouve que le pire cas théorique est très lent à atteindre, et valide l'efficacité pratique de PRIM-LWE pour les standards de cryptographie post-quantique actuels.