Ce que le tore interdit

Cette séance remonte §5.1 avant le schéma, et c'est délibéré. La section rassemble les réductions qu'un adversaire peut effectuer gratuitement, et chacune explique une clause de la définition posée en séance 2. Lire la construction avant cette section, c'est accepter une forme sans savoir ce qu'elle interdit.

À lire avant la séance

§5.1 en entier, puis dans §5.3 le paragraphe Galois descent, and the necessity of uniform $A$. Gardez sous les yeux la Définition 2 et le Corollaire 1 : chaque paragraphe de §5.1 y renvoie.

La lecture commutative, et pourquoi elle est exclue

C'est l'argument central de l'article, et il tient en trois lignes. Supposons que l'on conditionne $A$ à se trouver dans le tore $M(\mathcal{A})$. L'instance dégénère alors en

où la norme $N_{\mathcal{A}/R_q} = \det \circ\, M$ transforme la relation $bs = e$ en $N(b)\,N(s) = N(e)$ — une instance NTRU sur $R_q$, en dimension $n$ et non $nk$. Le seuil surétiré serait alors gouverné par $n$, ce qui est fatal : toute la marge gagnée disparaîtrait.

D'où la clause de la Définition 2 qui exige $A$ uniforme sur toute l'algèbre $\mathcal{M}_k$. La relation devient alors une différence et non un quotient, et aucune application de norme ne s'applique. L'article en tire une consigne d'implémentation explicite : tout raccourci qui biaiserait $A$ vers le tore est interdit.

La linéarisation par l'adjointe n'est pas compétitive

Deuxième route naturelle : multiplier la relation par $\mathrm{adj}(M_s)$ pour obtenir

qui est linéaire dans les entrées de $\mathrm{adj}(M_s)$. Le gain est illusoire : on troque la non-linéarité contre un secret élevé au carré, dont les entrées sont des formes de degré $k-1$ en celles de $s$, donc de taille $\eta^{k-1}$, et cela dans une dimension gonflée. À $k = 2$ l'instance obtenue a un secret de variance $\Theta(\eta^2)$ dans la même dimension, donc une exigence de facteur de Hermite strictement pire que l'attaque primale directe. Elle est écartée, et l'inflation empire à $k \geqslant 3$.

CRT et attaques par slot

Elles sont bloquées par le non-scindage, et uniquement par lui. C'est le point de méthode le plus important de la séance : si $\alpha$ était scindé, $\mathcal{A}$ contiendrait un facteur isomorphe à $R_q$ et la brièveté se testerait un slot CRT à la fois, ce qui récupérerait la clé. Le Lemme 1 fait de $\mathcal{A}$ un produit de grands corps $\mathbb{F}_{q^k}$, et la brièveté devient une condition globale en coefficients.

L'article insiste, et il faut le répéter en séance : c'est le seul endroit de tout le travail où le non-scindage sert. C'est une condition de dureté en amont, pas un ingrédient de réduction — la Remarque 9 confirmera que le théorème IND-CPA ne l'invoque pas.

Sous-sélection de colonnes

Le réseau primal se tronque à $m \leqslant k$ colonnes retenues, ce qui donne une dimension $nk(1+m)$ et un volume $q^{nkm}$. À chaque jeu de paramètres de l'article, l'optimum est $m^{*} = 1$ : l'attaquant n'utilise qu'une colonne.

C'est le visage numérique d'un fait structurel. Les $k^2 - k$ coordonnées d'erreur supplémentaires ne portent aucune entropie fraîche sur $s$ ; elles gonflent la clé publique et le chiffré sans contribuer à la dureté. Le schéma de la séance suivante se contente donc de cesser de les publier, et son réseau d'attaque tronqué coïncide exactement avec le régime $m^{*} = 1$. Aucune sécurité n'est perdue — et c'est cette observation, non une hypothèse supplémentaire, qui le justifie.

Rigidité, et ce que « résoudre » veut dire

§5.1 se clôt en rappelant le Corollaire 1 et l'Heuristique 6 : les solutions courtes forment le module planté $\mathcal{P}$, et le premier minimum hors de $\mathcal{P}$ se situe à $\approx \sqrt{d/2\pi e}\,q^{k/(k+1)}$. Tous les jeux de paramètres sont choisis de sorte que $\sqrt{d}\max(\beta_s,\beta_e)$ soit bien en dessous de cette valeur. Retrouver n'importe quelle solution courte, c'est donc retrouver la clé à un scalaire près.

La descente galoisienne

L'algèbre $\mathcal{A} = R_q[y]/(y^k - \alpha)$ porte un groupe d'automorphismes, engendré à $k = 2$ par $\sigma : (a_0, a_1) \mapsto (a_0, -a_1)$. Comme $\sigma(s)$ est aussi court que $s$, un adversaire pourrait espérer élargir le module planté en lui adjoignant les images de Galois du témoin, rendant le sous-réseau dense plus dense.

L'espoir échoue, et l'obstruction est encore l'uniformité de $A$. En posant $D := \mathrm{diag}(1,-1)$, on a $M_{\sigma(a)} = D\,M_a\,D^{-1}$ pour tout $a \in \mathcal{A}$, et conjuguer la relation par $D$ donne

L'image de Galois du témoin est bien courte — mais c'est un témoin pour l'instance $(DAD^{-1}, \sigma(t))$, pas pour $(A,t)$. Puisque $A$ est uniforme sur $\mathcal{M}_k$, on a $DAD^{-1} \neq A$ sauf sur une fraction négligeable d'instances : le conjugué n'apporte aucun vecteur au réseau que l'adversaire détient réellement.

C'est une seconde raison, indépendante de celle de la norme, d'exiger l'uniformité — et elle se vérifie en une ligne. Si $A$ avait été tiré du tore, ou de tout ensemble invariant par conjugaison par $D$, la conclusion s'inverserait.

Point de discussion

L'article revendique explicitement de ne pas être exhaustif : il affirme seulement que les deux cassures publiées de la famille procèdent par découverte de sous-réseau dense, que c'est ce que §5.6 modélise et mesure, et que la route algébrique évidente se ferme pour une raison vérifiable en une ligne. Est-ce une posture méthodologique satisfaisante ? Confrontez-la à la Table 10, qui liste ce qui n'est pas modélisé, et demandez-vous quel autre argument on pourrait raisonnablement exiger d'un premier tour de cryptanalyse.

À retenir