Théorie de la structure et rigidité

Une hypothèse nouvelle sans réduction du pire cas ne vaut que ce que sa théorie de la structure établit. Cette séance couvre tout ce qui se démontre inconditionnellement sur $\mathrm{NTC}$ — et, non moins important, ce qui ne s'en démontre pas.

À lire avant la séance

§3.4 à §3.6, c'est-à-dire les Lemmes 4 à 6, le Corollaire 1, l'Heuristique 6, la Proposition 1 et les Remarques 3 et 4. Puis §3.9 et sa Table 2.

Chaque composante est uniforme

Le Lemme 4 est presque trop court pour être remarqué, et il est décisif. Pour $(s,e)$ fixé avec $s$ inversible, si $A$ est uniforme sur $\mathcal{M}_k$ alors $t = (M_s A + e)M_s^{-1}$ est exactement uniforme sur $\mathcal{M}_k$. La preuve tient en deux phrases : $A \mapsto M_s A M_s^{-1}$ est une bijection, et $t$ est la translation d'une variable uniforme par une matrice fixée.

La conséquence est qu'il n'y a rien à chercher dans les marges. Toute l'information réside dans la corrélation jointe de $(A,t)$ : aucun test statistique appliqué à $t$ seul — spectre, déterminant, distribution des coefficients — ne peut obtenir le moindre avantage. À cet égard, la forme décisionnelle se comporte comme le NTRU décisionnel.

L'invariance le long du tore, et sa limite

Le Lemme 5 dit que pour tout $c \in \mathcal{A}$, arbitraire et non nécessairement court, l'application $(A,t) \mapsto (A + M_c,\; t + M_c)$ préserve la distribution d'instance avec le même témoin. La preuve tient en une ligne, le commutateur s'annulant parce que $c$ et $s$ vivent tous deux dans l'algèbre commutative $\mathcal{A}$.

La Remarque 3 en tire une forme normale — on peut supposer la projection de $A$ sur $M(\mathcal{A})$ nulle — puis énonce sa limite, et c'est le point à ne pas laisser passer : l'orbite est de codimension $k^2 - k$ seulement. Ce n'est donc pas une auto-réduction aléatoire complète, et aucune réduction du pire cas au cas moyen n'est connue pour $\mathrm{NTC}$. Le séminaire y reviendra en séance 8, où une route conjecturale contourne entièrement le problème.

Le commutant générique

Le Lemme 6 est le cœur technique. Pour $A$ uniforme, en notant $\mathcal{C}(A_i)$ le centralisateur du $i$-ième slot NTT,

avec probabilité au moins $1 - n\,\omega(k)\,q^{-k^2/2}$, où $\omega(k)$ compte les diviseurs premiers distincts de $k$. Au $k = 2$ déployé cela se lit $1 - n\,q^{-2}$.

La preuve mérite d'être suivie au tableau, car elle est plus soignée qu'il n'y paraît : elle borne directement l'intersection, sans hypothèse de régularité sur $A_i$, et couvre donc aussi les slots dérogatoires — ceux dont le centralisateur est strictement plus grand que $\mathbb{F}_q[A_i]$.

Le module planté, et l'unicité des solutions courtes

Le Corollaire 1 en déduit la description complète des solutions. En écrivant une solution quelconque $s' = su$ avec $u := s^{-1}s' \in \mathcal{A}$, on obtient $e' = M_s\,[A, M_u] + e\,M_u$. Deux cas, et deux seulement : si $u \in R_q$ le commutateur s'annule et $(s',e') = (us, ue)$ ; sinon le Lemme 6 donne $[A, M_u] \neq 0$, et $M_s[A,M_u]$ est heuristiquement de taille $\Theta(q)$, incompatible avec la borne de brièveté.

Les seules solutions courtes structurellement garanties forment donc le module planté de rang un

de rang $n$ sur $\mathbb{Z}$ à l'intérieur d'une dimension $nk(1+k)$. C'est l'analogue des rotations triviales $(x^j f, x^j g)$ de NTRU — à ceci près que le plant occupe une fraction $1/\bigl(k(1+k)\bigr)$ de la dimension au lieu de $1/2$. Notez soigneusement ce chiffre : il concerne le réseau complet, et la séance 7 montrera que ce n'est pas celui qui gouverne l'attaque.

L'Heuristique 6 ferme le dispositif en situant le premier minimum hors du plant à $\lambda_1(\Lambda \setminus \mathcal{P}) \approx \sqrt{d/2\pi e}\; q^{k/(k+1)}$. Les bornes de brièveté sont choisies bien en dessous, de sorte que résoudre au sens de la Définition 3, c'est retrouver la clé à un scalaire court près — l'analogue exact de « NTRU retrouve $(f,g)$ à une unité près ».

Recherche et décision

La Proposition 1 établit que la recherche se réduit à la décision : un adversaire résolvant $\mathrm{NTC}$-Search avec avantage $\varepsilon$ fournit un distingueur contre $\mathrm{NTC}$-Dec d'avantage au moins $\varepsilon - \mathrm{negl}$. L'argument est direct — sur une instance uniforme le réseau ne porte aucun plant, donc par l'heuristique gaussienne aucune solution valide n'existe.

La Remarque 4 énonce la réciproque, et il faut la prendre au sérieux : elle est ouverte. La machinerie standard de réduction recherche-vers-décision pour (Ring-)LWE repose sur la re-randomisation d'échantillons fraîchement tirés, ce qui n'est pas disponible ici : une clé définit une unique instance, et le Lemme 5 ne re-randomise que le long d'une orbite de codimension $k^2 - k$. La situation est celle de NTRU, où la variante décisionnelle doit être supposée séparément.

Point de discussion

L'article fait reposer la bonne position du problème de recherche sur une heuristique gaussienne, pas sur un théorème. Prenez trente minutes pour délimiter précisément ce que l'Heuristique 6 suppose, et demandez-vous ce qui se passerait si elle était fausse : la Définition 3 resterait-elle bien posée ? La Proposition 1 survivrait-elle ? Comparez ensuite avec le rôle que jouent les heuristiques analogues dans l'analyse de NTRU — la question n'est pas de savoir si l'on s'appuie sur des heuristiques, mais si l'on sait lesquelles.

À retenir