An alternative approach towards attacks against fully-split PLWE instances

Resumen Técnico: Un Enfoque Alternativo hacia Ataques contra Instancias PLWE Totalmente Descompuestas

Planteamiento del Problema
El problema de la Aprendizaje con Errores sobre Polinomios (PLWE, por sus siglas en inglés) es una piedra angular de la criptografía post-cuántica, a menudo favorecido por su eficiencia sobre el Ring-LWE debido a sus propiedades algebraicas estructuradas. Sin embargo, esta estructura introduce vulnerabilidades potenciales. Trabajos previos, notablemente [5, 6] y generalizados en [2], introdujeron "ataques basados en raíces" que explotan la existencia de factores polinómicos específicos (conocidos como factores ideales-$n$, $x^n - a$) sobre cuerpos finitos. Estos ataques utilizan homomorfismos de evaluación y operadores de traza para distinguir las muestras de PLWE de las distribuciones uniformes.

Si bien [2] generalizó estos ataques a polinomios que se factorizan sobre extensiones de cuerpo, una pregunta crítica permaneció abierta: ¿Podría un atacante eludir la falta de factores vulnerables en una instancia PLWE "segura" mapeándola mediante un isomorfismo de anillo a una instancia "vulnerable" (una que posea factores ideales-$n$ adecuados), realizando el ataque allí, e infiriendo la seguridad de la instancia original? Este artículo investiga si tal estrategia de migración mediante isomorfismos ofrece una ventaja significativa contra las instancias PLites PLWE totalmente descompuestas.

Metodología
Los autores emplean un enfoque algebraico riguroso para analizar la viabilidad de transferir muestras de PLWE entre diferentes anillos polinómicos. La metodología procede en dos fases principales:

1. Generalización de la Factorización Arbitraria: El artículo explora primero la extensión de los ataques basados en raíces a polinomios sin factores ideales-$n$. Utilizando el Lema 1, los autores demuestran que los operadores de traza pueden definirse sobre factores irreducibles arbitrarios. Sin embargo, muestran que la probabilidad de éxito de tales ataques depende fuertemente del número de coeficientes con valor cero en el factor, lo cual es típicamente bajo para polinomios arbitrarios, haciendo que el ataque sea impracticable en el caso general.

2. Análisis de Isomorfismo en Entornos Totalmente Descompuestos: El núcleo del trabajo se centra en el "enfoque de isomorfismo". Los autores consideran dos polinomios, $f(x)$ y $g(x)$, ambos de grado $N$ e irreducibles sobre $\mathbb{Z}[x]$, que comparten la misma "estructura de factorización" sobre $\mathbb{F}_q$ (es decir, se descomponen en factores irreducibles de los mismos grados).

   • Construcción: Utilizando el Teorema de la Resta China, construyen un isomorfismo explícito $\psi$ entre los anillos $R_q = \mathbb{F}_q[x]/(f(x))$ y $R'_q = \mathbb{F}_q[x]/(g(x))$. En el caso totalmente descompuesto (donde ambos polinomios se factorizan completamente en términos lineales), este isomorfismo se representa mediante el producto de matrices de Vandermonde: $\psi = V_g^{-1} \cdot V_f$.
   • Análisis de Distorsión: Los autores analizan el efecto de aplicar este isomorfismo a las muestras de PLWE seguido de una evaluación en una raíz $\beta$ de $g(x)$. Prueban que la evaluación resultante es matemáticamente equivalente a evaluar la muestra original en una raíz correspondiente $\alpha$ de $f(x)$.
   • Prueba de Unicidad: Una parte significativa de la metodología implica probar que cualquier isomorfismo de anillo entre tales anillos polinómicos totalmente descompuestos debe tomar esta forma específica (composición de homomorfismos de evaluación y el isomorfismo construido). Esto se establece a través de los Lemas 2, 3 y 4, y el Teorema 1.

Contribuciones Clave

• Prueba Formal de Invarianza de Isomorfismo: El artículo proporciona una prueba formal de que, para instancias PLWE totalmente descompuestas, cualquier intento de migrar muestras a un entorno vulnerable mediante un isomorfismo de anillo no genera nuevas vulnerabilidades. El ruido (error) introducido por el isomorfismo distorsiona las muestras de tal manera que las condiciones de distinguibilidad son idénticas a las de la instancia original.
• Caracterización de Isomorfismos de Anillo: Los autores caracterizan el conjunto completo de isomorfismos entre anillos polinómicos totalmente descompuestos, mostrando que están determinados únicamente por el mapeo de las raíces. Esto demuestra que no existe un isomorfismo "oculto" que pueda eludir la distorsión del ruido.
• Extensión a la Factorización Arbitraria: El trabajo aclara que, si bien los ataques basados en raíces pueden aplicarse teóricamente a polinomios sin factores ideales-$n$, la falta de restricciones estructurales (específicamente el número de coeficientes cero) limita severamente su probabilidad de éxito, cerrando efectivamente la puerta a esta generalización como una amenaza práctica.

Resultados

• Distorsión del Ruido: La aplicación de un isomorfismo $\psi$ seguido de una evaluación en una raíz $\beta$ de $g(x)$ resulta en la expresión $b(\beta) = \sum a_j \alpha^j$, donde $\alpha$ es la raíz correspondiente de $f(x)$. Esto demuestra que el ataque en el entorno transformado es matemáticamente idéntico al ataque en el entorno original.
• Fracaso de la Estrategia de Migración: El análisis confirma que si un ataque basado en raíces falla en la instancia PLWE original (debido a un alto ruido o falta de distinguibilidad), también fallará en cualquier instancia isomórfica. El isomorfismo no "limpia" el ruido; más bien, preserva la dificultad subyacente del problema.
• Análisis de Raíces Específicas: El artículo analiza casos específicos donde la raíz de evaluación $\beta$ es $0$, $1$ o una raíz arbitraria. En todos los casos, la evaluación resultante se reduce a la evaluación del polinomio original en una raíz correspondiente, confirmando que no se obtiene ninguna ventaja.

Significancia
El artículo concluye que la intuición respecto a la seguridad de las instancias PLWE totalmente descompuestas es correcta: si los ataques basados en raíces no tienen éxito contra una instancia PLWE inicial, seguirán sin tener éxito incluso si las muestras se transfieren a un entorno PLWE potencialmente más débil mediante isomorfismos de anillo.

Este resultado proporciona una fuente de confianza para la seguridad de las instancias PLWE totalmente descompuestas, que son comunes en construcciones criptográficas debido a su eficiencia (por ejemplo, en Transformadas de Número Teórico - NTT). El trabajo descarta eficazmente la "migración por isomorfismo" como un vector viable para generar nuevos ataques contra estas instancias específicas. Los autores señalan que, si bien este análisis es específico para polinomios totalmente descompuestos, cubre la gran mayoría de las instancias PLWE criptográficamente relevantes. El artículo no pretende resolver la seguridad de las instancias no totalmente descompuestas u otros vectores de ataque (como los ataques de ideales de Stickelberger mencionados en la introducción), sino que consolida la comprensión de los ataques basados en raíces dentro del dominio totalmente descompuesto.