Anneaux, non-scindage, et la définition de NTC

Cette séance pose l'objet. Elle demande de la patience : la définition de l'hypothèse tient en trois lignes, mais chacune de ses clauses est là pour fermer une attaque, et la séance 4 les reprendra une à une. L'exercice ici est de comprendre ce qui est défini, sans encore savoir pourquoi.

À lire avant la séance

§2 en entier — Définition 1, Lemmes 1 à 3, Remarque 1, Table 1 — puis §3.1 à §3.3 (Définitions 2 à 4, Hypothèse 5), et enfin §3.7 et §3.8, deux sous-sections courtes qui situent l'objet dans le paysage.

Deux familles d'anneaux

L'article travaille sur deux familles, et il faut savoir laquelle sert à quoi.

La première est la cyclotomique en puissance de deux, avec $n \in \{256, 512\}$. La seconde vaut $\mathbb{Z}[x]/\varPhi_{3N}(x)$ pour $N = 2^a \cdot 3$ ; à $N = 384$ c'est $\varPhi_{1152}$, l'analogue de demi-taille de l'anneau popularisé par NTTRU. La réduction n'y est plus une permutation signée et les produits s'étendent : la seconde famille coûte 50 % de variance en plus à degré égal. Les facteurs $\mathsf{E}$ mesurent exactement cette croissance, et la dernière colonne dit ce que coûte le twist.

Sur cette base on définit l'algèbre qui porte tout l'article :

un $R_q$-module libre de rang $k$. La multiplication à gauche plonge $\mathcal{A}$ dans l'algèbre matricielle $\mathcal{M}_k = M_k(R_q)$ par la représentation régulière $M : a \mapsto M_a$ ; son image est une sous-algèbre commutative maximale, un tore maximal de $\mathrm{GL}_k$. À $k = 2$ elle s'écrit explicitement

Le non-scindage, et ce qu'il bloque

C'est la condition centrale. $\alpha$ est non scindé d'ordre $k$ si, dans chaque slot NTT $i$, le polynôme $y^k - \alpha_i$ est irréductible sur $\mathbb{F}_q$. Le Lemme 1 en tire la conséquence qui compte :

— un produit de grands corps, sans aucun facteur isomorphe à $R_q$. Sans cette condition, $\mathcal{A}$ contiendrait un facteur isomorphe à $R_q$, la brièveté se testerait un slot CRT à la fois, et la clé tomberait. Avec elle, la brièveté est une condition globale en coefficients. Retenez la formulation de l'article : le non-scindage est une condition de dureté en amont, pas un ingrédient de réduction — et la séance 4 montrera que c'est le seul endroit où il sert.

Le Lemme 2 complète : un élément de $\mathcal{A}$ est inversible si et seulement si son évaluation est non nulle dans chaque slot, et pour un tirage binomial centré la probabilité de non-inversibilité est au plus $n\,q^{-k}$. C'est ce qui rend la boucle de rejet de la génération de clés négligeable.

Pourquoi le twist est $x$

Le Lemme 3 donne le critère, valable dans les deux familles : en notant $M$ l'ordre multiplicatif de $x$ modulo le polynôme définissant — $M = 2n$ dans la première famille, $M = 3N$ dans la seconde — le twist $\alpha = x$ est non scindé d'ordre 2 si et seulement si

Ce qui se spécialise en $q \equiv 2n+1 \pmod{4n}$ et, pour $\varPhi_{1152}$, en $q \equiv 1153 \pmod{2304}$. Les deux conditions raffinent la condition de NTT complète $M \mid q-1$ et sont compatibles avec elle.

La Remarque 1 explique pourquoi on ne choisit pas autre chose. Le tentant $\alpha = x^{N/2}$, racine primitive sixième de l'unité, échoue toujours : son ordre est 6, et $12 \mid 3N \mid q-1$, donc c'est un carré dans chaque slot. Quant aux constantes, la plus petite admissible est $\alpha = 3$ dans la famille en puissance de deux — d'expansion 10 — et $\alpha = 5$ dans $\varPhi_{1152}$ — d'expansion 26. Face à cela, $\alpha = x$ ne coûte qu'un facteur 2. Non-scindage et croissance du bruit tirent donc dans le même sens, ce qui n'allait pas de soi.

L'hypothèse

La distribution d'instance (Définition 2) tire $A$ uniforme sur $\mathcal{M}_k$, un secret court $s$ inversible dans $\mathcal{A}$, une erreur courte $e$ dans $\mathcal{M}_k$, et publie

Une matrice uniforme conjuguée par un élément court du tore, perturbée additivement. La forme de recherche demande de retrouver un témoin court ; la forme de décision demande de distinguer $(A,t)$ d'un couple uniforme.

La Remarque 2 mérite un temps d'arrêt : exiger $s' \in \mathcal{A}$ plutôt que $s' \in \mathcal{M}_k$ est constitutif du problème. Sans cette contrainte, tout vecteur court du noyau approché de l'opérateur de Sylvester $X \mapsto tX - XA$ conviendrait, et de tels vecteurs abondent. L'hypothèse est précisément que le secret est confiné au commutant.

Les deux bornes du paysage

Deux sous-sections courtes situent l'objet, et il faut les avoir en tête pour tout le reste.

La famille multi-instances. La Définition 7 tire un unique $s$, puis $\ell$ couples $(A_j, t_j)$. La monotonie est immédiate : la dureté de $\mathrm{NTC}^{(1)}$ découle de celle de $\mathrm{NTC}^{(\ell)}$ pour tout $\ell \geqslant 1$. Le KEM n'utilise que $\ell = 1$, la forme la plus conservatrice — et l'article prévient que toute variante exposant plusieurs $t_j$ sous un même $s$ devrait être ré-estimée, l'analogue NTRU étant strictement plus faible.

Le cas $k = 1$. Le tore est alors l'anneau tout entier, $M$ est l'identité, et la relation se réduit à $t - A = e s^{-1}$ : du NTRU décisionnel après translation publique. La famille contient donc strictement NTRU, et tout jeu de paramètres hérite des contraintes connues de NTRU — en particulier l'analyse du régime surétiré n'est pas optionnelle.

Point de discussion

Le twist $\alpha = x$ est le seul choix où l'arithmétique et l'analyse du bruit s'accordent : il est presque gratuit à calculer, et il coûte le plus petit facteur d'expansion admissible. Est-ce une coïncidence heureuse, ou la contrainte de non-scindage sélectionne-t-elle structurellement les twists de petit ordre ? Reformulez la Remarque 1 pour en décider, puis demandez-vous ce qu'un $k \geqslant 3$ changerait à l'argument.

À retenir