An alternative approach towards attacks against fully-split PLWE instances

Résumé Technique : Une approche alternative des attaques contre les instances PLWE entièrement scindées (Fully-Split)

Énoncé du Problème
Le problème du Polynomial Learning With Errors (PLWE) est une pierre angulaire de la cryptographie post-quantique, souvent privilégié pour son efficacité par rapport au Ring-LWE en raison de ses propriétés algébriques structurées. Cependant, cette structure introduit de potentielles vulnérabilités. Des travaux antérieurs, notamment [5, 6] et généralisés dans [2], ont introduit des « attaques basées sur les racines » qui exploitent l'existence de facteurs polynomiaux spécifiques (connus sous le nom de facteurs idéaux $n$, $x^n - a$) sur des corps finis. Ces attaques utilisent des homomorphismes d'évaluation et des opérateurs de trace pour distinguer les échantillons PLWE des distributions uniformes.

Alors que [2] a généralisé ces attaques aux polynômes se factorisant sur des extensions de corps, une question ouverte cruciale demeurait : un attaquant pourrait-il contourner l'absence de facteurs vulnérables dans une instance PLWE « sûre » en la projetant, via un isomorphisme d'anneau, vers une instance « vulnérable » (possédant des facteurs idéaux $n$ appropriés), en effectuant l'attaque sur celle-ci, puis en déduisant la sécurité de l'instance originale ? Ce document examine si une telle stratégie de migration via des isomorphismes offre un avantage significatif contre les instances PLWE entièrement scindées.

Méthodologie
Les auteurs emploient une approche algébrique rigoureuse pour analyser la faisabilité du transfert d'échantillons PLWE entre différents anneaux polynomiaux. La méthodologie se déroule en deux phases principales :

1. Généralisation de la Factorisation Arbitraire : Le document explore d'abord l'extension des attaques basées sur les racines à des polynômes sans facteurs idéaux $n$. En utilisant le Lemme 1, les auteurs démontrent que des opérateurs de trace peuvent être définis sur des facteurs irréductibles arbitraires. Cependant, ils montrent que la probabilité de succès de ces attaques dépend fortement du nombre de coefficients nuls dans le facteur, ce qui est typiquement faible pour des polynômes arbitraires, rendant l'attaque impraticable dans le cas général.

2. Analyse d'Isomorphisme dans les Contextes Entièrement Scindés : Le cœur du travail se concentre sur l'« approche par isomorphisme ». Les auteurs considèrent deux polynômes, $f(x)$ et $g(x)$, tous deux de degré $N$ et irréductibles sur $\mathbb{Z}[x]$, qui partagent la même « structure de factorisation » sur $\mathbb{F}_q$ (c'est-à-dire qu'ils se décomposent en facteurs irréductibles de mêmes degrés).

   • Construction : En utilisant le théorème des restes chinois, ils construisent un isomorphisme explicite $\psi$ entre les anneaux $R_q = \mathbb{F}_q[x]/(f(x))$ et $R'_q = \mathbb{F}_q[x]/(g(x))$. Dans le cas entièrement scindé (où les deux polynômes se factorisent complètement en termes linéaires), cet isomorphisme est représenté par le produit de matrices de Vandermonde : $\psi = V_g^{-1} \cdot V_f$.
   • Analyse de la Distorsion : Les auteurs analysent l'effet de l'application de cet isomorphisme à des échantillons PLWE suivi d'une évaluation en une racine $\beta$ de $g(x)$. Ils prouvent que l'évaluation résultante est mathématiquement équivalente à l'évaluation de l'échantillon original en une racine correspondante $\alpha$ de $f(x)$.
   • Preuve d'Unicité : Une partie importante de la méthodologie consiste à prouver que tout isomorphisme d'anneau entre de tels anneaux polynomiaux entièrement scindés doit prendre cette forme spécifique (composition d'homomorphismes d'évaluation et de l'isomorphisme construit). Ceci est établi via les Lemmes 2, 3 et 4, et le Théorème 1.

Contributions Clés

• Preuve Formelle de l'Invariance par Isomorphisme : Le document fournit une preuve formelle que pour les instances PLWE entièrement scindées, toute tentative de migration d'échantillons vers un cadre vulnérable via un isomorphisme d'anneau ne génère pas de nouvelles vulnérabilités. Le bruit (erreur) introduit par l'isomorphisme distord les échantillons de telle sorte que les conditions de distinguabilité résultantes sont identiques à celles de l'instance originale.
• Caractérisation des Isomorphismes d'Anneau : Les auteurs caractérisent l'ensemble complet des isomorphismes entre les anneaux polynomiaux entièrement scindés, montrant qu'ils sont déterminés de manière unique par la correspondance des racines. Cela prouve qu'aucun isomorphisme « caché » n'existe qui pourrait contourner la distorsion du bruit.
• Extension à la Factorisation Arbitraire : Le travail clarifie que, bien que les attaques basées sur les racines puissent théoriquement être appliquées à des polynômes sans facteurs idéaux $n$, l'absence de contraintes structurelles (spécifiquement le nombre de coefficients nuls) limite sévèrement leur probabilité de succès, fermant ainsi la porte à cette généralisation en tant que menace pratique.

Résultats

• Distorsion du Bruit : L'application d'un isomorphisme $\psi$ suivie d'une évaluation en une racine $\beta$ de $g(x)$ donne l'expression $b(\beta) = \sum a_j \alpha^j$, où $\alpha$ est la racine correspondante de $f(x)$. Cela démontre que l'attaque sur le cadre transformé est mathématiquement identique à l'attaque sur le cadre original.
• Échec de la Stratégie de Migration : L'analyse confirme que si une attaque basée sur les racines échoue sur l'instance PLWE originale (en raison d'un bruit élevé ou d'un manque de distinguabilité), elle échouera également sur toute instance isomorphe. L'isomorphisme ne « nettoie » pas le bruit ; il préserve la difficulté sous-jacente du problème.
• Analyse de Racines Spécifiques : Le document analyse des cas spécifiques où la racine d'évaluation $\beta$ est $0$, $1$, ou une racine arbitraire. Dans tous les cas, l'évaluation se réduit à l'évaluation du polynôme original en une racine correspondante, confirmant qu'aucun avantage n'est obtenu.

Signification
Le document conclut que l'intuition concernant la sécurité des instances PLWE entièrement scindées est correcte : si les attaques basées sur les racines sont infructueuses contre une instance PLWE initiale, elles resteront infructueuses même si les échantillons sont transférés vers un cadre PLWE potentiellement plus faible via des isomorphismes d'anneaux.

Ce résultat fournit une source de confiance pour la sécurité des instances PLWE entièrement scindées, qui sont courantes dans les constructions cryptographiques en raison de leur efficacité (par exemple, dans les Transformées de Noyau Numérique - NTT). Ce travail écarte efficacement la « migration par isomorphisme » comme un vecteur viable pour générer de nouvelles attaques contre ces instances spécifiques. Les auteurs notent que bien que cette analyse soit spécifique aux polynômes entièrement scindés, elle couvre la vaste majorité des instances PLWE pertinentes pour la cryptographie. Le document ne prétend pas résoudre la sécurité des instances non entièrement scindées ou d'autres vecteurs d'attaque (tels que les attaques d'idéal de Stickelberger mentionnées dans l'introduction), mais plutôt solidifie la compréhension des attaques basées sur les racines au sein du domaine entièrement scindé.