Ce séminaire lit un article de bout en bout : A Torus-Structured Generalisation of NTRU, IACR ePrint 2026/1642. Cette première séance n'en couvre encore rien — elle installe le socle sans lequel la contribution n'a pas d'objet. Le phénomène central de l'article, le régime surétiré, n'est pas un détail technique de NTRU : c'est la contrainte que l'article cherche à desserrer, et tout le reste en découle.

À lire avant la séance

L'introduction en entier, §1 à §1.4. Gardez §1.2 Limitations ouverte pendant tout le séminaire : les séances 5 à 8 en vérifient les items un à un — et vous constaterez que l'un d'eux ne tient plus, ce qui est en soi un enseignement sur la lecture des prépublications.

NTRU, et l'économie qui l'expose

NTRU reste, après un quart de siècle, la construction à réseaux la plus économique dont on dispose. Sa clé publique est un unique élément d'anneau, ses opérations quelques multiplications polynomiales, et sa sécurité repose sur un énoncé d'une simplicité désarmante : étant donné $h = g/f$ dans $R_q$ avec $f$ et $g$ courts, retrouver $(f,g)$.

Cette économie est aussi son exposition. Le réseau NTRU porte un module planté de rang $n$ dans une dimension $2n$ — exactement la moitié de l'espace ambiant. C'est cette densité qui gouverne le phénomène surétiré.

Les constructions module-LWE standardisées à la place — Kyber, devenu ML-KEM, et Dilithium, devenu ML-DSA — échappent au phénomène en n'ayant aucun plant : leur clé publique est pseudo-aléatoire par réduction depuis un problème du pire cas. Le prix est une clé publique et un chiffré qui croissent avec le rang du module. Les deux familles occupent donc les deux extrémités d'un compromis, et la question qui motive l'article est de savoir si l'intervalle entre elles contient quelque chose.

L'attaque primale, et l'estimation 2016

La sécurité contre la réduction de réseaux se mesure par l'attaque primale uSVP sous l'estimation standard de 2016 : un blocksize $\beta$ suffit dès que

avec des coûts core-SVP de $0{,}292\,\beta$ en classique et $0{,}265\,\beta$ en quantique. Retenez cette formule : c'est le seul estimateur employé dans tout l'article, et la séance 6 sera consacrée à sa calibration et à ses limites.

Le régime surétiré

Passé un seuil de module, un second mécanisme prend le pas sur la récupération de clé : la découverte de sous-réseau dense trouve le module planté plus vite que l'estimation générique ne le prédit. On parle d'événement DSD, par opposition à l'événement SKR de récupération de clé, et le module auquel les deux se croisent est le point de fatigue.

Trois conséquences, toutes structurantes pour l'article :

• Le seuil a été cartographié assez précisément pour que les paramètres déployés s'en tiennent à l'écart ; pour NTRU circulant ternaire, l'ajustement publié est $q_{\mathrm{fat}} \approx 0{,}004\,n^{2{,}484}$.
• La marge est donc une contrainte de conception, et non une conséquence de la conception.
• Elle interdit le régime de grand $q$ que la correction d'un schéma de chiffrement réclame naturellement — un plafond qui vient se refermer sur le plancher imposé par la correction.

C'est exactement cette fenêtre, entre le plancher de correction et le plafond de fatigue, que l'article cherche à élargir. Tenez-en la définition pour acquise : la séance 7 y reviendra pour la mesurer.

La question de l'article

Entre un plant dont l'économie se paie par un régime surétiré, et une construction pseudo-aléatoire dont la garantie du pire cas se paie par la taille, y a-t-il quelque chose d'utile ? La réponse proposée conserve le plant de NTRU et change ce dans quoi il est planté : le secret est confiné à un tore maximal non déployé de $\mathrm{GL}_k(R_q)$, et l'instance devient une conjugaison bruitée plutôt qu'un quotient.

Deux conséquences structurelles sont annoncées dès l'introduction, et le séminaire les suivra jusqu'à leur mesure : le module planté n'occupe plus qu'une fraction $1/(2k)$ de la dimension du réseau publié au lieu de $1/2$, et le raccourci par la norme qui gouverne le régime surétiré devient indisponible.

Point de discussion

Lisez §1.2 Limitations à voix haute en séance et dressez-en la liste au tableau. Les auteurs y annoncent ce qu'ils ne prouvent pas, ce qu'ils mesurent hors du domaine validé de leur modèle, et ce qu'ils n'ont pas fait. Deux questions à garder pour la séance 8 : cette discipline est-elle la norme dans les prépublications que vous lisez ? Et une hypothèse annoncée comme « non portante mais achetable » est-elle un objet acceptable dans un contexte de standardisation ?

À retenir

Cette séance pose l'objet. Elle demande de la patience : la définition de l'hypothèse tient en trois lignes, mais chacune de ses clauses est là pour fermer une attaque, et la séance 4 les reprendra une à une. L'exercice ici est de comprendre ce qui est défini, sans encore savoir pourquoi.

À lire avant la séance

§2 en entier — Définition 1, Lemmes 1 à 3, Remarque 1, Table 1 — puis §3.1 à §3.3 (Définitions 2 à 4, Hypothèse 5), et enfin §3.7 et §3.8, deux sous-sections courtes qui situent l'objet dans le paysage.

Deux familles d'anneaux

L'article travaille sur deux familles, et il faut savoir laquelle sert à quoi.

La première est la cyclotomique en puissance de deux, avec $n \in \{256, 512\}$. La seconde vaut $\mathbb{Z}[x]/\varPhi_{3N}(x)$ pour $N = 2^a \cdot 3$ ; à $N = 384$ c'est $\varPhi_{1152}$, l'analogue de demi-taille de l'anneau popularisé par NTTRU. La réduction n'y est plus une permutation signée et les produits s'étendent : la seconde famille coûte 50 % de variance en plus à degré égal. Les facteurs $\mathsf{E}$ mesurent exactement cette croissance, et la dernière colonne dit ce que coûte le twist.

Sur cette base on définit l'algèbre qui porte tout l'article :

un $R_q$-module libre de rang $k$. La multiplication à gauche plonge $\mathcal{A}$ dans l'algèbre matricielle $\mathcal{M}_k = M_k(R_q)$ par la représentation régulière $M : a \mapsto M_a$ ; son image est une sous-algèbre commutative maximale, un tore maximal de $\mathrm{GL}_k$. À $k = 2$ elle s'écrit explicitement

Le non-scindage, et ce qu'il bloque

C'est la condition centrale. $\alpha$ est non scindé d'ordre $k$ si, dans chaque slot NTT $i$, le polynôme $y^k - \alpha_i$ est irréductible sur $\mathbb{F}_q$. Le Lemme 1 en tire la conséquence qui compte :

— un produit de grands corps, sans aucun facteur isomorphe à $R_q$. Sans cette condition, $\mathcal{A}$ contiendrait un facteur isomorphe à $R_q$, la brièveté se testerait un slot CRT à la fois, et la clé tomberait. Avec elle, la brièveté est une condition globale en coefficients. Retenez la formulation de l'article : le non-scindage est une condition de dureté en amont, pas un ingrédient de réduction — et la séance 4 montrera que c'est le seul endroit où il sert.

Le Lemme 2 complète : un élément de $\mathcal{A}$ est inversible si et seulement si son évaluation est non nulle dans chaque slot, et pour un tirage binomial centré la probabilité de non-inversibilité est au plus $n\,q^{-k}$. C'est ce qui rend la boucle de rejet de la génération de clés négligeable.

Pourquoi le twist est $x$

Le Lemme 3 donne le critère, valable dans les deux familles : en notant $M$ l'ordre multiplicatif de $x$ modulo le polynôme définissant — $M = 2n$ dans la première famille, $M = 3N$ dans la seconde — le twist $\alpha = x$ est non scindé d'ordre 2 si et seulement si

Ce qui se spécialise en $q \equiv 2n+1 \pmod{4n}$ et, pour $\varPhi_{1152}$, en $q \equiv 1153 \pmod{2304}$. Les deux conditions raffinent la condition de NTT complète $M \mid q-1$ et sont compatibles avec elle.

La Remarque 1 explique pourquoi on ne choisit pas autre chose. Le tentant $\alpha = x^{N/2}$, racine primitive sixième de l'unité, échoue toujours : son ordre est 6, et $12 \mid 3N \mid q-1$, donc c'est un carré dans chaque slot. Quant aux constantes, la plus petite admissible est $\alpha = 3$ dans la famille en puissance de deux — d'expansion 10 — et $\alpha = 5$ dans $\varPhi_{1152}$ — d'expansion 26. Face à cela, $\alpha = x$ ne coûte qu'un facteur 2. Non-scindage et croissance du bruit tirent donc dans le même sens, ce qui n'allait pas de soi.

L'hypothèse

La distribution d'instance (Définition 2) tire $A$ uniforme sur $\mathcal{M}_k$, un secret court $s$ inversible dans $\mathcal{A}$, une erreur courte $e$ dans $\mathcal{M}_k$, et publie

Une matrice uniforme conjuguée par un élément court du tore, perturbée additivement. La forme de recherche demande de retrouver un témoin court ; la forme de décision demande de distinguer $(A,t)$ d'un couple uniforme.

La Remarque 2 mérite un temps d'arrêt : exiger $s' \in \mathcal{A}$ plutôt que $s' \in \mathcal{M}_k$ est constitutif du problème. Sans cette contrainte, tout vecteur court du noyau approché de l'opérateur de Sylvester $X \mapsto tX - XA$ conviendrait, et de tels vecteurs abondent. L'hypothèse est précisément que le secret est confiné au commutant.

Les deux bornes du paysage

Deux sous-sections courtes situent l'objet, et il faut les avoir en tête pour tout le reste.

La famille multi-instances. La Définition 7 tire un unique $s$, puis $\ell$ couples $(A_j, t_j)$. La monotonie est immédiate : la dureté de $\mathrm{NTC}^{(1)}$ découle de celle de $\mathrm{NTC}^{(\ell)}$ pour tout $\ell \geqslant 1$. Le KEM n'utilise que $\ell = 1$, la forme la plus conservatrice — et l'article prévient que toute variante exposant plusieurs $t_j$ sous un même $s$ devrait être ré-estimée, l'analogue NTRU étant strictement plus faible.

Le cas $k = 1$. Le tore est alors l'anneau tout entier, $M$ est l'identité, et la relation se réduit à $t - A = e s^{-1}$ : du NTRU décisionnel après translation publique. La famille contient donc strictement NTRU, et tout jeu de paramètres hérite des contraintes connues de NTRU — en particulier l'analyse du régime surétiré n'est pas optionnelle.

Point de discussion

Le twist $\alpha = x$ est le seul choix où l'arithmétique et l'analyse du bruit s'accordent : il est presque gratuit à calculer, et il coûte le plus petit facteur d'expansion admissible. Est-ce une coïncidence heureuse, ou la contrainte de non-scindage sélectionne-t-elle structurellement les twists de petit ordre ? Reformulez la Remarque 1 pour en décider, puis demandez-vous ce qu'un $k \geqslant 3$ changerait à l'argument.

À retenir

Une hypothèse nouvelle sans réduction du pire cas ne vaut que ce que sa théorie de la structure établit. Cette séance couvre tout ce qui se démontre inconditionnellement sur $\mathrm{NTC}$ — et, non moins important, ce qui ne s'en démontre pas.

À lire avant la séance

§3.4 à §3.6, c'est-à-dire les Lemmes 4 à 6, le Corollaire 1, l'Heuristique 6, la Proposition 1 et les Remarques 3 et 4. Puis §3.9 et sa Table 2.

Chaque composante est uniforme

Le Lemme 4 est presque trop court pour être remarqué, et il est décisif. Pour $(s,e)$ fixé avec $s$ inversible, si $A$ est uniforme sur $\mathcal{M}_k$ alors $t = (M_s A + e)M_s^{-1}$ est exactement uniforme sur $\mathcal{M}_k$. La preuve tient en deux phrases : $A \mapsto M_s A M_s^{-1}$ est une bijection, et $t$ est la translation d'une variable uniforme par une matrice fixée.

La conséquence est qu'il n'y a rien à chercher dans les marges. Toute l'information réside dans la corrélation jointe de $(A,t)$ : aucun test statistique appliqué à $t$ seul — spectre, déterminant, distribution des coefficients — ne peut obtenir le moindre avantage. À cet égard, la forme décisionnelle se comporte comme le NTRU décisionnel.

L'invariance le long du tore, et sa limite

Le Lemme 5 dit que pour tout $c \in \mathcal{A}$, arbitraire et non nécessairement court, l'application $(A,t) \mapsto (A + M_c,\; t + M_c)$ préserve la distribution d'instance avec le même témoin. La preuve tient en une ligne, le commutateur s'annulant parce que $c$ et $s$ vivent tous deux dans l'algèbre commutative $\mathcal{A}$.

La Remarque 3 en tire une forme normale — on peut supposer la projection de $A$ sur $M(\mathcal{A})$ nulle — puis énonce sa limite, et c'est le point à ne pas laisser passer : l'orbite est de codimension $k^2 - k$ seulement. Ce n'est donc pas une auto-réduction aléatoire complète, et aucune réduction du pire cas au cas moyen n'est connue pour $\mathrm{NTC}$. Le séminaire y reviendra en séance 8, où une route conjecturale contourne entièrement le problème.

Le commutant générique

Le Lemme 6 est le cœur technique. Pour $A$ uniforme, en notant $\mathcal{C}(A_i)$ le centralisateur du $i$-ième slot NTT,

avec probabilité au moins $1 - n\,\omega(k)\,q^{-k^2/2}$, où $\omega(k)$ compte les diviseurs premiers distincts de $k$. Au $k = 2$ déployé cela se lit $1 - n\,q^{-2}$.

La preuve mérite d'être suivie au tableau, car elle est plus soignée qu'il n'y paraît : elle borne directement l'intersection, sans hypothèse de régularité sur $A_i$, et couvre donc aussi les slots dérogatoires — ceux dont le centralisateur est strictement plus grand que $\mathbb{F}_q[A_i]$.

Le module planté, et l'unicité des solutions courtes

Le Corollaire 1 en déduit la description complète des solutions. En écrivant une solution quelconque $s' = su$ avec $u := s^{-1}s' \in \mathcal{A}$, on obtient $e' = M_s\,[A, M_u] + e\,M_u$. Deux cas, et deux seulement : si $u \in R_q$ le commutateur s'annule et $(s',e') = (us, ue)$ ; sinon le Lemme 6 donne $[A, M_u] \neq 0$, et $M_s[A,M_u]$ est heuristiquement de taille $\Theta(q)$, incompatible avec la borne de brièveté.

Les seules solutions courtes structurellement garanties forment donc le module planté de rang un

de rang $n$ sur $\mathbb{Z}$ à l'intérieur d'une dimension $nk(1+k)$. C'est l'analogue des rotations triviales $(x^j f, x^j g)$ de NTRU — à ceci près que le plant occupe une fraction $1/\bigl(k(1+k)\bigr)$ de la dimension au lieu de $1/2$. Notez soigneusement ce chiffre : il concerne le réseau complet, et la séance 7 montrera que ce n'est pas celui qui gouverne l'attaque.

L'Heuristique 6 ferme le dispositif en situant le premier minimum hors du plant à $\lambda_1(\Lambda \setminus \mathcal{P}) \approx \sqrt{d/2\pi e}\; q^{k/(k+1)}$. Les bornes de brièveté sont choisies bien en dessous, de sorte que résoudre au sens de la Définition 3, c'est retrouver la clé à un scalaire court près — l'analogue exact de « NTRU retrouve $(f,g)$ à une unité près ».

Recherche et décision

La Proposition 1 établit que la recherche se réduit à la décision : un adversaire résolvant $\mathrm{NTC}$-Search avec avantage $\varepsilon$ fournit un distingueur contre $\mathrm{NTC}$-Dec d'avantage au moins $\varepsilon - \mathrm{negl}$. L'argument est direct — sur une instance uniforme le réseau ne porte aucun plant, donc par l'heuristique gaussienne aucune solution valide n'existe.

La Remarque 4 énonce la réciproque, et il faut la prendre au sérieux : elle est ouverte. La machinerie standard de réduction recherche-vers-décision pour (Ring-)LWE repose sur la re-randomisation d'échantillons fraîchement tirés, ce qui n'est pas disponible ici : une clé définit une unique instance, et le Lemme 5 ne re-randomise que le long d'une orbite de codimension $k^2 - k$. La situation est celle de NTRU, où la variante décisionnelle doit être supposée séparément.

Point de discussion

L'article fait reposer la bonne position du problème de recherche sur une heuristique gaussienne, pas sur un théorème. Prenez trente minutes pour délimiter précisément ce que l'Heuristique 6 suppose, et demandez-vous ce qui se passerait si elle était fausse : la Définition 3 resterait-elle bien posée ? La Proposition 1 survivrait-elle ? Comparez ensuite avec le rôle que jouent les heuristiques analogues dans l'analyse de NTRU — la question n'est pas de savoir si l'on s'appuie sur des heuristiques, mais si l'on sait lesquelles.

À retenir