Séminaire — une généralisation de NTRU structurée par un tore · C1 L'hypothèse et sa structure · Chapitre 1 · 3 h

Le socle NTRU et le régime surétiré

NTRU, son réseau de densité 1/2, l'attaque primale et le point de fatigue : sans eux, la contribution de l'article n'a pas d'objet.

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.

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

\sqrt{\beta/d}\,\lVert v \rVert \;\leqslant\; \delta_\beta^{\,2\beta-d-1}\,\mathrm{vol}^{1/d}, \qquad \delta_\beta = \left(\frac{(\pi\beta)^{1/\beta}\beta}{2\pi e}\right)^{1/(2(\beta-1))}

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.

Quiz · 1 question

Qu'est-ce qui, dans NTRU, rend la découverte de sous-réseau dense efficace passé un certain module ?

La petite taille des coefficients de f et g
La densité du plant : un module de rang n dans une dimension 2n
Le fait que la clé publique soit un quotient plutôt qu'une différence

Réponse : C'est la densité qui gouverne le phénomène, et c'est précisément la quantité que l'article modifie. La forme de quotient joue un autre rôle — elle ouvre le raccourci par la norme, objet de la séance 4 — mais elle n'est pas ce qui rend le sous-réseau dense découvrable.

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.

Quiz · 1 question

Pourquoi les constructions module-LWE standardisées ne connaissent-elles pas de point de fatigue ?

Parce que leur modulus est toujours choisi petit
Parce qu'elles n'ont aucun module planté : leur clé publique est pseudo-aléatoire
Parce que leur réseau est de dimension trop grande pour être réduit

Réponse : Sans plant, il n'y a pas de sous-réseau dense à découvrir, donc pas de seuil. Le prix est ailleurs : une clé publique et un chiffré qui croissent avec le rang du module. C'est le compromis dont l'article explore l'intervalle.

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

Flashcards · 4 cartes