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

La forme du schéma n'est pas libre. L'algèbre en impose une partie — c'est l'objet de l'Annexe E — et la cryptanalyse de la séance précédente en autorise une autre, prise ici à crédit et honorée en séance 7. Cette séance suit ces deux déterminations jusqu'à l'IND-CCA.

À lire avant la séance

§4 en entier, des leviers de §4.1 aux tailles de §4.10, en passant par les Algorithmes 1 à 5 et les Théorèmes 1 et 2. Puis l'Annexe D, courte, sur la probabilité d'échec exacte, et les deux premiers paragraphes de l'Annexe E sur ce que l'algèbre force.

Ce que l'algèbre force

Deux contraintes précèdent tout choix de conception.

La trappe rescale par $s$, donc l'encodage est $p$-adique. La seule opération secrète dont dispose le receveur est la multiplication par $M_s$ : tout ce qui est extrait se trouve donc mis à l'échelle par $s$. Un encodage à la Kyber, $\Delta\cdot m$ avec $\Delta = \lceil q/2 \rceil$, ferait récupérer $\Delta\, s m$ dont la norme est bien trop grande pour éviter le repli modulo $q$. On suit donc la route NTRU : tous les termes parasites sont rendus nuls modulo $p$, et le message se lit modulo un petit premier.

L'aléa de chiffrement doit vivre dans $\mathcal{A}$. Le déchiffrement ne se referme que si l'aléa de l'émetteur commute avec $M_s$. Par le Lemme 6, le commutant d'une matrice générique ne rencontre $M(\mathcal{A})$ qu'en les scalaires : l'aléa doit donc être pris dans $\mathcal{A}$ lui-même, et non comme une matrice courte arbitraire de $\mathcal{M}_k$.

Les trois leviers

Troncature de ligne. En imposant $s \equiv 1 \pmod p$ et en restreignant le message à la première coordonnée, on obtient $\mathrm{coef}(sm) \equiv (m_0, 0, \ldots, 0) \pmod p$ : le déchiffrement ne lit que la première coordonnée. Le receveur n'a donc besoin que d'une ligne de $t$ et d'une ligne de $c_2$, d'où une clé publique de $nk$ coefficients et un chiffré de $2nk$ — au lieu de $nk^2$ et $nk(k+1)$. Le réseau d'attaque tronqué coïncide exactement avec le régime $m^{*} = 1$ de la séance 4 : rien n'est perdu.

Encodage MSB, pour la compression seule. Le budget de bruit est identique ; le gain est que l'erreur d'arrondi entre additivement comme un bruit ordinaire, là où un encodage LSB détruirait le résidu modulo $p$. Deux limites méritent d'être nommées. La clé publique tronquée n'est pas compressible : son erreur d'arrondi multiplie un produit de deux secrets, et un seul bit brise la correction. Et le chiffré ne tolère qu'une compression modérée, $d = 11$ à 12 bits, parce qu'à la différence du $v$ de Kyber il multiplie un secret et non un haché.

Distributions découplées. Une largeur unique partout est sous-optimale : élargir $\chi_r$ durcit la seconde hypothèse à un coût linéaire dans le budget de bruit, alors que $\chi_f$ y entre quadratiquement. Le découplage en trois largeurs $(\eta_f, \eta_r, \eta_{s'})$ récupère la catégorie 3, qui échouerait autrement.

Le levier qu'on ne peut pas tirer. La Remarque 6 mérite d'être lue en séance : annuler les coordonnées d'erreur que l'attaque n'utilise pas est dangereux. La relation publique est colonne par colonne une équation linéaire en $\mathrm{coef}(s)$ ; mettre une coordonnée à zéro impose une contrainte exacte qui, combinée à la brièveté de $s$, récupère la clé. Les leviers changent ce qui est publié, jamais la façon dont on échantillonne.

Correction, et la probabilité d'échec exacte

Le Lemme 7 donne l'identité de déchiffrement, la Proposition 2 la condition de correction, et l'équation (5) la variance coordonnée par coordonnée. Jusque-là, la mécanique est classique.

§4.5 l'est beaucoup moins, et c'est la partie de §4 à ne pas survoler. La borne gaussienne sous-estime la queue d'une somme de produits de variables bornées. Le calcul exact, par convolution et avec le terme d'arrondi énuméré plutôt qu'approché, coûte 2 à 9 bits sur la variance et 2 à 3 de plus sur la queue : le $\delta$ gaussien est optimiste de 5 à 12 bits à ces paramètres.

La conséquence est concrète. À la catégorie 1, la marge passe de 16 bits à 4 — et c'est précisément ce qui rend la contrainte de correction mordante dans le réglage de la séance 8, où un jeu sélectionné contre le $\delta$ gaussien s'avère inadmissible. Le Lemme 8 clôt la section sur une note plus légère : la clé $p$-adique est gratuite, le facteur $p$ pouvant être ignoré dans l'analyse de sécurité.

La seconde hypothèse

Il faut être clair là-dessus, car le résumé peut induire en erreur : la sécurité passive ne repose pas sur $\mathrm{NTC}$ seule. La pseudo-aléatoirité de la clé publique ne cache pas le message ; il faut encore que le chiffré soit pseudo-aléatoire. La Définition 8 isole cette seconde hypothèse décisionnelle, $\mathsf{cLWE}_{\mathcal{A}}$ — exactement l'analogue de la situation NTRU, où le NTRU décisionnel se combine à une hypothèse de type LWE sur le quotient devenu uniforme.

La Remarque 8 en établit la plausibilité, et vaut d'être détaillée : l'échantillon tronqué en colonne est précisément du module-LWE de rang $k$ sur $R_q$ ; l'échantillon tronqué en ligne est du ring-LWE sur $\mathcal{A}$, qui se trouve être l'anneau cyclotomique de degré $nk$ — $\varPhi_{4n}$ dans la famille en puissance de deux, et l'anneau $\varPhi_{2304}$ à la catégorie 3. Ce sont deux objets standards, et la seule structure jointe est le secret $r$ partagé, c'est-à-dire le cadre ordinaire du LWE à échantillons multiples.

De l'IND-CPA à l'IND-CCA

Le Théorème 1 borne l'avantage par la somme des deux hypothèses, en deux sauts de jeu : le premier remplace la ligne publiée de $t$ par de l'uniforme — un distingueur tronque un défi $\mathrm{NTC}$-Dec — le second remplace le chiffré, qui est exactement une instance $\mathsf{cLWE}_{\mathcal{A}}$ tronquée à $\ell = 2$ sous secret commun.

Deux remarques encadrent le résultat. La Remarque 9 souligne que la réduction est serrée et n'invoque ni l'Heuristique 6 ni le non-scindage — ceux-ci servent au problème de recherche ; le non-scindage reste cependant nécessaire en amont, faute de quoi l'attaque CRT récupère la clé et $\mathrm{NTC}$-Dec est simplement fausse. La Remarque 10 précise que les deux sauts ne consomment que ce que le schéma publie, la corrélation de colonnes du schéma non tronqué n'étant jamais exposée.

La transformation de Fujisaki–Okamoto à rejet implicite donne enfin l'IND-CCA dans le ROM. Le terme $q_G\,\delta$ du Théorème 2 est ce qui impose $\delta \leqslant 2^{-140}$ : à $\lambda = 128$ et $q_G \leqslant 2^{64}$, la queue doit être coupée à six ou sept écarts-types.

Point de discussion

La Remarque 11 chiffre ce que coûterait la conception naïve : publier les $k$ lignes, encoder $p$-adiquement, une seule largeur de bruit — soit 2,3 à 2,7 fois la clé publique et 1,5 à 2 fois le chiffré, à sécurité égale. Autrement dit, la compacité annoncée du schéma tient pour bonne moitié à une lecture fine de sa propre cryptanalyse. Est-ce une pratique saine ? Elle crée une dépendance : si §5.1 se révélait fautive sur $m^{*} = 1$, le schéma perdrait sa compacité sans que sa sécurité soit d'abord en cause. Discutez cette dette, que l'article assume explicitement en parlant de crédit.

À retenir