Paramètres, implémentation, statut de l'hypothèse

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