Resumen Técnico: Complejidad de la Resolución de Sistemas de Ecuaciones del Mismo Grado

Planteamiento del Problema

La seguridad de numerosos esquemas criptográficos, particularmente en la criptografía multivariante y en entornos post-cuánticos, depende de la dureza computacional de resolver sistemas de ecuaciones polinómicas multivariantes sobre cuerpos finitos. La complejidad de resolver tales sistemas mediante métodos de bases de Gröbner está gobernada principalmente por el grado de regularidad ($d_{reg}$) y el grado de resolución (solving degree). Mientras que el grado de regularidad proporciona un límite superior en la complejidad de los cálculos de bases de Gröbner, a menudo es difícil de calcular o estimar para sistemas de tamaño criptográfico.

La práctica común se basa en el supuesto heurístico de que los sistemas son semirregulares (o criptográficamente semirregulares), lo que produce fórmulas explícitas para el grado de regularidad. Sin embargo, este supuesto no siempre es válido; existen elecciones de parámetros y cuerpos donde no existe una secuencia semirregular. En consecuencia, existe la necesidad de límites superiores probados, no heurísticos, para el grado de regularidad y el grado de resolución que se apliquen a sistemas donde el grado de regularidad es finito, sin depender del supuesto de semirregularidad.

Metodología

Los autores abordan el problema utilizando herramientas del álgebra conmutativa, centrándose específicamente en sistemas donde el ideal generado por las partes de grado superior de los polinomios contiene una secuencia regular de $m$ polinomios en un grado $D$ dado.

1. Marco de trabajo: El artículo considera un sistema $F = \{f_1, \dots, f_m\}$ de $m$ polinomios en $n$ variables sobre un cuerpo $F$. El análisis asume que las partes de grado superior $f_1^{top}, \dots, f_m^{top}$ son linealmente independientes y que el sistema es regular en el grado $D$ (lo que significa que el ideal generado por las partes de grado superior contiene una secuencia regular de $n$ polinomios de grado $D$).
2. Reducción a Ideales LPP: Para acotar la regularidad de Castelnuovo-Mumford (que es igual al grado de regularidad cuando este es finito), los autores utilizan la Conjetura de Eisenbud-Green-Harris (EGH). Esta conjetura postula que, entre todos los ideales homogéneos que contienen una secuencia regular de grados específicos, el ideal Lex-Plus-Powers (LPP) posee la regularidad máxima.
3. Análisis Combinatorio: Los autores construyen ideales LPP específicos asociados con los parámetros dados ($n, m, D$). Al analizar la estructura de estos ideales bajo el orden lexicográfico, determinan la regularidad del ideal LPP, que sirve como un límite superior para la regularidad del sistema original (condicionado a la Conjetura EGH).
4. Ecuaciones de Cuerpo: La metodología se extiende a sistemas aumentados con ecuaciones de cuerpo ($x_i^q - x_i$), lo cual es crítico para sistemas sobre cuerpos finitos $\mathbb{F}_q$, particularmente cuando el grado de las ecuaciones $D$ es mayor o igual al tamaño del cuerpo $q$.

Contribuciones Clave y Resultados

1. Límites Superiores para Sistemas Regulares en Grado $D$ (Sin Ecuaciones de Cuerpo)

El Teorema 23 proporciona un límite superior ajustado para el grado de regularidad de un sistema de $m$ ecuaciones de grado $D$ en $n$ variables, asumiendo que el sistema es regular en el grado $D$.

• El límite depende del número de ecuaciones ($m$), variables ($n$) y grado ($D$).
• La fórmula implica la identificación de enteros únicos $k$ y $t$ tales que $m-n$ cae dentro de un intervalo específico definido por sumas combinatorias ($\sigma_{k,t}$).
• El límite resultante es: $d_{reg}(F) \le (D - t) + (n - k)(D - 1)$.
• Este límite es ajustado (sharp) para todos los valores de $m, n, D$ y se cumple en sistemas donde las partes de grado superior forman un ideal LPP específico.

El Corolario 27 traduce esto en un límite superior para el grado de resolución para algoritmos mutantes:
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. Límites Superiores para Sistemas con Ecuaciones de Cuerpo

El artículo aborda el caso en el que se añaden ecuaciones de cuerpo al sistema, lo cual es esencial cuando $D \ge q$.

• Proposición 31: Para sistemas muy sobredeterminados (donde $m$ excede la dimensión del espacio de polinomios módulo las ecuaciones de cuerpo), el grado de regularidad es exactamente $D$.
• Teorema 33: Para sistemas donde $q \le D \le n(q-1)$ y las partes de grado superior son linealmente independientes módulo las ecuaciones de cuerpo, los autores proporcionan un límite superior para el grado de regularidad.
  • El límite se deriva analizando la posición del $m$-ésimo monomio en el orden lexicográfico de los monomios de grado $D$ módulo $(x_1^q, \dots, x_n^q)$.
  • El límite se expresa en términos de $B = q - t + (n - k)(q - 1)$, donde $k$ y $t$ son determinados por el intervalo que contiene a $m$.
  • Dependiendo de condiciones específicas de $m, D$ y $t$, el límite es $B$ o $B-1$.

El Corolario 34 especializa estos resultados para sistemas binarios ($q=2$), proporcionando fórmulas simplificadas para el grado de regularidad y el grado de resolución para sistemas de grado $D$ sobre $\mathbb{F}_2$.

3. Aplicación a Esquemas Específicos

Los autores aplican sus límites a esquemas criptográficos concretos:

• Cubic Simple Matrix: Derivan un límite probado $d_{reg} \le 2n - 1$, que es el primer límite probado para este sistema, contrastando con las estimaciones heurísticas previas.
• Unbalanced Oil and Vinegar (UOV): Los límites se aplican a sistemas UOV sobre $\mathbb{F}_2$, demostrando cómo se comporta el grado de regularidad cuando se incluyen las ecuaciones de cuerpo.

Significancia y Reivindicaciones

El artículo reivindica su significancia principalmente al proporcionar límites probados y no heurísticos para la complejidad de la resolución de sistemas polinómicos.

• Fiabilidad: A diferencia de las estimaciones basadas en el supuesto de semirregularidad (que pueden fallar para ciertos parámetros), estos límites se aplican a cualquier sistema donde el grado de regularidad es finito y el sistema es regular en un grado dado.
• Generalidad: Los resultados se aplican a sistemas sobre cuerpos arbitrarios y cubren tanto el caso con como sin ecuaciones de cuerpo.
• Ajuste (Sharpness): Los límites se describen como "ajustados", lo que significa que son alcanzados por sistemas específicos (ideales LPP), ofreciendo una estimación realista del peor caso para el análisis de seguridad.
• Limitaciones: Los autores reconocen explícitamente que sus límites son generalmente menos ajustados (es decir, más altos) que los obtenidos bajo la heurística de semirregularidad. Sin embargo, argumentan que este compromiso es necesario para evitar supuestos no probados, particularmente en escenarios donde no existen secuencias semirregulares.

El trabajo no propone nuevos algoritmos o implementaciones experimentales, sino que establece límites teóricos sobre la complejidad de los métodos existentes de bases de Gröbner (tanto estándar como mutantes) para una amplia clase de sistemas polinómicos relevantes para la criptografía.