Une hypothèse sans réduction du pire cas vaut exactement ce que vaut sa cryptanalyse. §5 l'énonce sans détour, et fait trois choses : elle cartographie la surface d'attaque — vue en séance 4 — elle fixe un seul estimateur, calibré par référence externe, et elle dit ce que cet estimateur ne modélise pas. Cette séance couvre les deux dernières.

À lire avant la séance

§5.2, §5.4 et §5.5, avec les Tables 3 à 5. Puis les Annexes A et B, qui portent respectivement la mesure sous réduction et le remplacement de l'hypothèse de série géométrique. La Remarque 12 est courte et décide du signe de toute la section : ne la sautez pas.

La calibration

Tout chiffre de sécurité de l'article sort d'un unique estimateur, calibré en le faisant tourner sur les instances module-LWE de Kyber et en comparant à leurs coûts core-SVP publiés.

L'accord est à 1,2 bit près, et l'estimateur est uniformément et légèrement optimiste. C'est la précision à laquelle tous les chiffres de la séance 8 doivent être lus, et l'article énonce en conséquence ses revendications comme des parités sous estimateur partagé, non comme des coûts absolus.

La méthode a une limite que les auteurs formulent eux-mêmes : calibrer vérifie qu'on calcule la même chose que les autres, pas que le calcul soit juste.

L'estimateur sous réduction

L'Annexe A répond à cette limite en confrontant l'estimateur à de la réduction réelle, sur des instances réduites du réseau de clé du KEM lui-même.

La forme employée pour produire les chiffres publiés est la première : elle sur-estime le blocksize dont un attaquant a besoin, de 9 à 20 unités, soit 3 à 6 bits de coût core-SVP. C'est le sens défavorable. La forme remise à l'échelle, elle, suit la réduction de près.

Largeurs inégales, et le retrait

Pourquoi deux formes ? Parce que secret et erreur n'ont pas la même largeur. Le secret du réseau est $s = 1 + p\,s'$, pas $s'$ ; l'erreur, elle, n'est pas mise à l'échelle par $p$, puisque le schéma compact publie $e_1$ et non $p\,e_1$. Il en résulte $\sigma_s/\sigma_e = 2{,}45$, le plus grand rapport de tout l'article — et nul chez Kyber, où les deux formes coïncident, ce qui explique que la question ne se pose pas là-bas.

Le remède standard est de remettre le bloc secret à l'échelle par $\omega := \sigma_e/\sigma_s$ avant d'appliquer l'estimation. Et cela baisse l'estimation au lieu de la relever.

Les auteurs en tirent une conclusion qu'il faut lire mot à mot, car c'est le mouvement le plus important de toute la cryptanalyse : ils ne révisent pas les jeux de paramètres, mais retirent la lecture selon laquelle les chiffres cités seraient conservateurs. Sur les éléments disponibles, ils sont optimistes, des montants ci-dessus.

L'attaque hybride

L'attaque hybride de Howgrave-Graham devine $g$ coordonnées d'un secret étroit par rencontre au milieu et résout le problème résiduel en dimension $d - g$. Elle mord exactement là où poussent les leviers de §4.1 : il faut donc la modéliser, non l'écarter. Deux modèles circulent, et ils divergent de dizaines de bits.

Le modèle strict suppose une réduction uSVP fraîche pour chaque devinette. Appliqué à Kyber-512, il prédit un gain hybride de 22 bits sur l'attaque primale — que les analyses publiées excluent. La calibration de §5.2 l'élimine donc d'elle-même, et il n'est conservé qu'en colonne de stress.

Le modèle Babai/GSA, standard depuis Wunderer, suppose que BKZ tourne une fois sur la base résiduelle et que chaque devinette coûte un appel au plan le plus proche, qui réussit lorsque la plus petite norme de Gram–Schmidt dépasse l'écart-type du bruit d'un facteur $\tau$. Cette constante doit être ajustée :

Le tableau donne le coût hybride moins le coût primal : négatif signifie que l'hybride gagne. À $\tau = 1{,}0$ le modèle offrirait 20 à 28 bits sur Kyber, ce qui est exclu ; à $\tau = 3{,}0$ il ne concède rien et n'apprend rien. Le croisement est entre 1,5 et 2,0, et l'article adopte $\tau = 2{,}0$ — en notant explicitement que cette valeur se situe au croisement et non confortablement au-delà.

Et la conclusion qui compte

L'Annexe B ne s'arrête pas à la constante. Elle remplace l'hypothèse de série géométrique par un simulateur de profil, et vérifie l'un contre l'autre sur les profils de Gram–Schmidt réellement mesurés en §5.6. La GSA sur-estime la plus petite norme de Gram–Schmidt d'un facteur 1,31 en moyenne sur 34 cellules non dégénérées, là où le simulateur de Chen–Nguyen la reproduit à 0,98–1,09.

Recalculée avec le simulateur, l'attaque hybride ne mord à aucun jeu de paramètres : son coût passe au-dessus du coût primal partout, et l'optimum dégénère en pure devinette. La conclusion est donc que la sensibilité à $\tau$ — et l'ambiguïté de largeur qui l'accompagne — sont des artefacts de la GSA. L'attaque primale est la contrainte mordante à chaque jeu de paramètres de l'article, et la forme fermée n'est gardée qu'en modèle de stress.

Point de discussion

La calibration sur Kyber est utilisée deux fois, et de deux manières différentes : pour étalonner l'estimateur primal, puis pour écarter un modèle hybride au motif qu'il prédirait un gain que la littérature exclut. Le second usage est-il légitime ? Il revient à traiter le consensus publié sur Kyber comme une donnée expérimentale. Quelles en sont les conditions de validité, et que se passerait-il si ce consensus bougeait ?

À retenir

C'est la séance la plus lourde du séminaire, et l'article le dit lui-même : puisque tout l'intérêt de la structure de tore est d'élargir la fenêtre de module, cette sous-section porte plus de poids qu'aucune autre. C'est aussi la seule où la revendication centrale est mesurée plutôt qu'extrapolée.

À lire avant la séance

§5.6 en entier, avec la Figure 1 et les Tables 6 à 9, puis §5.7 et la Table 10. L'Annexe C, qui porte la calibration du banc et ses trois limites, est indispensable : sans elle les chiffres de §5.6 se lisent trop vite.

Une comptabilité à ne pas confondre

L'article ouvre §5.6 par un point de comptabilité, en prévenant qu'il est facile de s'y tromper. Il y a deux réseaux, et ils n'ont ni la même dimension ni la même densité.

Le réseau $\mathrm{NTC}$ complet a la dimension $nk(1+k)$ et porte un plant de rang $n$, soit une densité $1/\bigl(k(k+1)\bigr)$ — c'est le chiffre du Corollaire 1, vu en séance 3. Mais le schéma ne publie pas ce réseau : il n'expose qu'une ligne. Ce que l'attaquant tient réellement est

dont la densité vaut $1/(2k)$, soit $1/4$ à $k = 2$, contre $1/2$ pour NTRU. C'est ce dernier chiffre qui gouverne l'attaque, et c'est celui contre lequel la simulation doit être menée. Les deux formules coïncident à $k = 1$, où l'on retrouve NTRU.

Structurellement, le réseau déployé est donc un réseau NTRU de demi-dimension $nk$ dont le plant est $k$ fois plus creux.

L'estimateur, généralisé

La méthode adapte l'estimateur DSD-PT de Ducas et van Woerden à un réseau $q$-aire portant un sous-réseau dense de rang arbitraire. Leur modèle est énoncé pour une dimension $2n$ avec un plant de rang $n$, de sorte que la demi-dimension, le rang du plant et leur différence coïncident ; la généralisation consiste précisément à démêler les trois. La quantité à généraliser est le co-rang $d - r$, et non la demi-dimension.

Deux validations précèdent tout chiffre, et l'article insiste pour qu'on les lise d'abord. Instancié sur la géométrie NTRU, l'estimateur généralisé reproduit l'original exactement : sur une grille de modules et de blocksizes, l'écart maximal sur la probabilité DSD est nul à la précision machine. Puis le point de fatigue qu'il prédit pour NTRU circulant ternaire reproduit l'ajustement publié $q_{\mathrm{fat}} \approx 0{,}004\,n^{2{,}484}$ — les rapports mesurés valent 0,0045, 0,0045, 0,0044 et 0,0042 — avec un blocksize de croisement dans la plage attendue.

L'expérience de densité

Vient alors l'expérience qui isole exactement ce qu'on veut isoler : on fixe la dimension du réseau et la norme du vecteur secret, et on ne fait varier que le rang du plant. À $k = 2$ les vecteurs plantés de $\mathrm{NTC}$ ont pour norme au carré $2N\sigma^2$, identique à celle de NTRU : la comparaison est propre.

Le plant plus creux repousse bien le point de fatigue, et le gain croît avec la dimension au lieu de se stabiliser à un facteur constant. Appliqué aux jeux déployés, l'événement DSD ne se déclenche jamais au module choisi : l'attaque procède par récupération de clé, à un blocksize concordant à 5 % près avec l'estimation primale, et le point de fatigue se situe bien au-dessus — 13,1, 16,1 et 18,6 bits de marge aux trois catégories.

La confirmation expérimentale

Les chiffres ci-dessus viennent d'un prédicteur. §5.6 les adosse à de la réduction réelle. On génère des instances du réseau publié et des témoins NTRU à dimension ambiante, déterminant, module et norme de vecteur planté identiques — tout invariant grossier coïncide, et les deux familles ne diffèrent que par le rang du plant.

Trois points de méthode font la valeur de l'expérience. Le test d'appartenance est exact — un vecteur est dans l'enveloppe rationnelle du plant si et seulement si tous les mineurs $v_i w_j - v_j w_i$ s'annulent — et vérifié en arithmétique entière : un accident numérique peut perdre un événement, jamais en inventer un. La règle de score suit la source, et un tour produisant les deux événements est compté SKR : elle ne peut donc que sous-compter DSD, des deux côtés. Enfin la réduction est celle de fplll, par énumération.

Les trois limites, à énoncer sans les adoucir

L'Annexe C les nomme, et le séminaire doit y consacrer un vrai temps.

• L'expérience règle l'ordre, pas la magnitude. Presque toutes les cellules qu'elle pourrait s'offrir croisent à $\beta < 20$, régime où LLL seul peut rendre le module planté entier ; l'ordre est robuste, la taille du gain ne l'est pas. Relocalisé sur un indicateur immunisé au bris d'égalité, le même gain vaut 1,68 bit au lieu de $\geqslant 4{,}86$.
• Le modèle est employé loin de son domaine validé. Ses auteurs l'ont vérifié jusqu'à $n \approx 200$ et $\beta \approx 60$ ; les jeux déployés sont à $nk = 512$–2048 avec des blocksizes de 130 à 390. L'expérience de l'article n'atteint que $2N \leqslant 256$. La taille des marges reste donc prédite, non observée.
• La probabilité DSD n'est pas monotone en $q$. En petite dimension l'estimateur sature et le rapport retombe : le point de fatigue doit être cherché par premier croisement et non par bissection, et les croisements sous $\beta = 20$ écartés comme dégénérés.

Ce qui n'est pas modélisé

§5.7 et la Table 10 ferment la section en listant ce que l'analyse ne couvre pas : les attaques algébriques propres au tore — la descente de trace donne du module-LWE de rang $k$ en dimension $nk$ sans descente vers $n$, mais c'est une observation et non une preuve — la corrélation de colonnes de la seconde hypothèse, que le schéma déployé n'expose jamais, l'exploitation adverse des échecs de déchiffrement, le multi-cible, et les canaux auxiliaires.

Point de discussion

L'article revendique un gain de 4,5 à 6,3 bits de module et une marge de 13 à 19 bits, tout en écrivant que la taille de ces marges reste prédite et non observée. Ces deux énoncés sont compatibles — mais dans quelle mesure la revendication de compacité du schéma en dépend-elle ? Reprenez la fenêtre de module de la séance 1 : si le gain réel était de 1,68 bit plutôt que de 4,5, quels jeux de paramètres de la séance 8 resteraient admissibles ?

À retenir

Dernière séance. Elle rassemble ce que l'article livre — trois jeux de paramètres et deux implémentations mesurées — ce qu'il propose d'acheter, et ce qu'il laisse ouvert. C'est aussi la séance où l'on revient sur la liste de §1.2 dressée le premier jour.

À lire avant la séance

§6.1 avec les Tables 11 et 12, puis §7 et §8 avec les Tables 13 et 14. L'Annexe F en entier, qui porte la route conjecturale, et la section Conclusion and open problems. L'Annexe E, sur les observations de conception, éclaire plusieurs choix restés inexpliqués jusqu'ici.

Les trois jeux

Face à ML-KEM — 800 / 1184 / 1568 octets de clé publique et 768 / 1088 / 1568 de chiffré — cela donne 1,08 à 1,16 fois la clé publique et 1,96 à 2,12 fois le chiffré. L'écart résiduel est concentré dans le chiffré et se retrace au terme $nk^2$ que la lecture matricielle impose.

La Table 12 détaille le réglage de la catégorie 1 contre le $\delta$ exact de la séance 5, et sa troisième ligne est instructive : le candidat $(4,8,3)$ atteint 118,3, soit exactement le chiffre de Kyber-512, mais sa queue exacte le place à $2^{-128,6}$. Il viole donc la contrainte de correction de 11 bits et n'est pas admissible. Un jeu sélectionné contre la borne gaussienne serait passé : c'est là que §4.5 mord.

La base du label

Le paragraphe The basis of the category-1 label est à lire intégralement en séance. Trois bits sous Kyber-512 sous un estimateur partagé, c'est un énoncé sur un exposant ; le label « catégorie 1 » est un énoncé sur un coût, dont le plancher est la recherche de clé sur AES-128. L'exposant core-SVP écarte délibérément les facteurs polynomiaux et le coût mémoire du criblage, que toute comptabilité au niveau des portes facture par dizaines de bits.

Les auteurs énoncent donc la dépendance plutôt que de la laisser implicite : NTC-KEM-512 est de catégorie 1 sous toute comptabilité du criblage où Kyber-512 l'est avec trois bits d'avance, et la revendication réellement défendue est relative. Un lecteur exigeant la marge complète de Kyber-512 doit attendre le changement d'anneau évoqué, ou déployer NTC-KEM-768.

Implémentation et mesures

Deux arbres C accompagnent l'article : un arbre de référence portable, dont le produit d'anneau est une convolution scolaire en $O(n^2)$ et l'inversion un divstep scalaire en temps constant, et un arbre AVX2 qui remplace le produit par la transformée, l'inversion scalaire par une inversion par voie, et le cœur Keccak par une permutation SIMD à quatre voies. Les deux, ainsi qu'une référence Python indépendante, émettent des vecteurs de test identiques octet pour octet.

Les accélérations de l'arbre AVX2 vont de 7,4× à 64× selon l'opération, la génération de clés gagnant le plus partout : la routine qui la dominait — l'inversion en temps constant de $s$ dans $\mathcal{A}$ — devient bon marché dans le domaine transformé. Face aux pairs NIST mesurés par le même banc, l'arbre AVX2 se situe à 5,5×, 4,8× et 3,6× la génération de clés de ML-KEM aux trois catégories, et devant tout pair non-module-LWE à chaque opération. La bande passante, elle, est indépendante de l'implémentation : environ 1,5× ML-KEM, ce que la troncature de la séance 5 avait précisément pour but d'acheter.

Ces mesures tranchent au passage la troisième des questions que l'Annexe G laissait à l'implémentation — l'étage radix-3 de la transformée de $\varPhi_{3N}$ ne rend pas la catégorie 3 disproportionnément lente : NTC-KEM-768 tourne à 0,96×, 0,91× et 0,83× les cycles de NTC-KEM-1024.

La route pire cas conjecturale

L'Annexe F développe l'alternative que Stehlé et Steinfeld avaient prise pour NTRU : élargir la distribution de clé jusqu'au paramètre de lissage du réseau de clé rend la clé publique statistiquement uniforme. L'hypothèse $\mathrm{NTC}$ disparaît alors entièrement de l'analyse, et l'IND-CPA repose sur la seule seconde hypothèse — laquelle, sous sa forme tronquée en ligne, est du module-LWE et hérite donc de la réduction au pire cas de Langlois–Stehlé.

Le prix est chiffré par la Proposition 3, à $n = 768$, $k = 2$ et $q = 10858753$ : une clé publique de 4640 octets et un chiffré de 9216, pour 193,6 bits sous l'estimateur partagé. Lus contre le jeu de catégorie 3, cela fait un facteur 3,4 sur la clé publique et 4,0 sur le chiffré — contre 5,4 et 6,0 face à la catégorie 1, mais cette dernière comparaison porte sur des niveaux de sécurité différents et les auteurs ne s'en servent pas.

La pénalité est nettement plus douce que son équivalent NTRU, et la raison est structurelle : le réseau de clé de $\mathrm{NTC}$ a déjà la dimension $2nk$ plutôt que $2n$, si bien que la largeur de lissage porte un facteur $1/\sqrt{nk}$ au lieu de $1/\sqrt{n}$. La Remarque 15 ajoute une observation qui vaut discussion : dans cette variante le vecteur secret est 3,4 fois plus long que le plus court vecteur générique attendu. Le plant disparaît, et avec lui tout le régime surétiré — §5.6 et la tension de l'Annexe E deviennent vacuous.

Ce que la conjecture recouvre

Il faut être précis, car c'est le point où l'article s'arrête. Le lemme de régularité qui rendrait le Théorème 3 rigoureux n'est pas établi pour les anneaux totalement déployés qu'exige la transformée employée. L'écart est chiffré : aux paramètres de la Proposition 3, la borne d'union disponible vaut $n/q = 2^{-13,8}$, contre les $2^{-127}$ qu'affirme le théorème — 113 bits de distance statistique de moins que revendiqué. L'énoncé manquant est donc isolé en Conjecture 1, et non passé sous silence.

La Remarque 16 ouvre une seconde route, qui n'a besoin d'aucune conjecture : en prenant $q \equiv 3$ ou $5 \pmod 8$, le polynôme $x^n+1$ se factorise en exactement deux irréductibles de degré $n/2$, l'ensemble exceptionnel se borne par $q^{-n/2}$ et le lemme s'applique tel quel. Le prix est la transformée — un seul étage de Cooley–Tukey, puis Karatsuba sur $\mathbb{F}_{q^{n/2}}$ — ce qui, pour une variante dont tout l'objet est d'échanger de l'efficacité contre une garantie, est le moins cher des deux prix.

Statut, et problèmes ouverts

$\mathrm{NTC}$ n'a pas de réduction au pire cas, et aucun membre de la famille NTRU-avec-erreurs n'en a. Sa forme décisionnelle doit être supposée séparément de sa forme de recherche. Le théorème de rigidité qui rend la recherche bien posée repose sur l'heuristique gaussienne, et les marges de fatigue viennent d'un prédicteur validé sur des figures NTRU publiées mais employé au-delà. Ce que l'article fournit est un premier tour de cryptanalyse, structuré de sorte qu'on voie précisément ce qui est modélisé et ce qui ne l'est pas ; ce qu'il ne fournit pas, ce sont les années d'examen qui rendraient l'hypothèse portante.

Les cinq problèmes ouverts, par poids décroissant : refaire l'expérience de §5.6 à l'échelle déployée ; démontrer la Conjecture 1, ou passer par la classe de modules qui s'en dispense ; établir une réduction entre les deux formes de l'hypothèse ; savoir si $k \geqslant 3$ apporte quelque chose une fois levée la comptabilité de chiffré qui force $k = 2$ ; et une implémentation — item que §8 a depuis partiellement réglé.

Point de discussion

Revenez à la liste de §1.2 dressée en séance 1 et cochez-la. Vous constaterez qu'un item — l'absence d'implémentation et de mesures — est contredit par §7 et §8, et que le préambule de l'Annexe G le répète encore. C'est une trace d'édition sans conséquence sur les résultats, et c'est un excellent sujet de discussion : comment lit-on une prépublication dont les sections ont été écrites à des moments différents ? Quelles parties d'un article faut-il relire quand une section est ajoutée ?

Terminez sur la question que l'article pose lui-même : une hypothèse « non portante mais achetable » — c'est-à-dire dont on peut se débarrasser à un coût chiffré — est-elle un objet acceptable ? Comparez avec la position de NTRU dans les années 2000, et avec ce que la standardisation a effectivement retenu.

À retenir