Cryptanalyse II : sous-réseau dense et point de fatigue

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