Infinite families of APN permutations in constrained trivariate classes over $\mathbb{F}_{2^m}$

Resumen Técnico: Familias Infinitas de Permutaciones APN en Clases Trivariadas Restringidas sobre $\mathbb{F}_{2^m}$

1. Planteamiento del Problema

La construcción de polinomios de permutación sobre campos finitos con una estructura algebraica simple en múltiples variables es un problema fundamental en la teoría de códigos y criptografía, específicamente en el diseño de cajas-S (S-boxes) para cifradores de bloque.

• Funciones APN: Una función es "Casi Perfecta No Lineal" (APN) si su uniformidad diferencial es 2 (el mínimo posible en característica par), lo que la hace óptima contra ataques de criptografía diferencial.
• El Desafío: Encontrar funciones que sean simultáneamente APN y permutaciones es notoriamente difícil. Solo se conocen unas pocas familias infinitas, y la existencia de tales funciones en todas las dimensiones pares sigue siendo una pregunta abierta.
• Contexto Reciente: Beierle y Leander descubrieron dos permutaciones APN "esporádicas" en dimensión 9 ($\mathbb{F}_{2^9}$). Li y Kaleyski (2024) generalizaron estos casos en dos familias infinitas de funciones trivariadas con coeficientes escalares en $\mathbb{F}_2$.
• Objetivo del Artículo: Extender el trabajo de Li y Kaleyski permitiendo que el coeficiente escalar $a$ varíe libremente sobre todo el campo $\mathbb{F}_{2^m}^*$ (en lugar de estar restringido a $\mathbb{F}_2$), investigando las familias generalizadas $G_a$ y $H_a$.

2. Metodología

Los autores emplean una combinación de teoría de campos finitos, geometría algebraica y análisis de sistemas de ecuaciones diferenciales.

• Definición de las Familias:
  Se estudian dos familias de funciones trivariadas $F: \mathbb{F}_{2^m}^3 \to \mathbb{F}_{2^m}^3$ con $q=2^i$ y $\gcd(i, m)=1$, $m$ impar:

  1. Familia $G_a$:
     $$G_a(x, y, z) = (x^{q+1} + ax^qz + yz^q, \ x^qz + y^{q+1}, \ xy^q + ay^qz + z^{q+1})$$
  2. Familia $H_a$:
     $$H_a(x, y, z) = (x^{q+1} + axy^q + yz^q, \ xy^q + z^{q+1}, \ x^qz + y^{q+1} + ay^qz)$$

• Reducción a Polinomios Univariables:
  El núcleo de la metodología consiste en demostrar que las propiedades de permutación y APN de estas funciones multivariadas están controladas por la ausencia de raíces en $\mathbb{F}_{2^m}^*$ de un polinomio univariable asociado.

  • Para $G_a$, se analiza el polinomio $Q_a(T) = T^{q^2+q+1} + aT + 1$.
  • Se demuestra que múltiples formas polinómicas ($P_a, P'_a, Q_a, R_a, S_a$) son equivalentes en raíces (tienen raíces en $\mathbb{F}_{2^m}^*$ simultáneamente).

• Herramientas de Geometría Algebraica:

  • Teorema de Lang-Weil y Límites de Hasse-Weil: Se utilizan para estimar el número de puntos racionales en curvas algebraicas definidas sobre $\mathbb{F}_{2^m}$, lo que permite establecer cotas inferiores sobre la cantidad de parámetros "buenos" (valores de $a$ que generan permutaciones APN).
  • Criterio de Rastreo (Trace Criterion): Se utiliza para analizar la solubilidad de ecuaciones de tipo Artin-Schreier en campos de característica 2.

• Análisis de Equivalencia:
  Se estudia la equivalencia bajo transformaciones afines (CCZ-equivalencia), lineales (EL-equivalencia) y diagonales. Se utiliza el teorema de restricción monomial de Shi et al. para demostrar que, bajo ciertas condiciones, la no-equivalencia diagonal implica no-equivalencia CCZ.

3. Contribuciones y Resultados Clave

A. Caracterización de Permutaciones y Propiedad APN

• Teorema Principal (2.7): Para la familia $G_a$, las siguientes condiciones son equivalentes:
  1. El polinomio $Q_a(T) = T^{q^2+q+1} + aT + 1$ no tiene raíces en $\mathbb{F}_{2^m}$.
  2. $G_a$ es una permutación sobre $\mathbb{F}_{2^m}^3$.
  3. $G_a$ es una función APN sobre $\mathbb{F}_{2^m}^3$.
• Resultado Análogo para $H_a$: Se demuestra que la familia $H_a$ comparte el mismo criterio de raíz (a través de la equivalencia de polinomios $R_a$ y $Q_a$). Por lo tanto, los mismos parámetros $a$ que hacen que $G_a$ sea una permutación APN también hacen que $H_a$ lo sea.

B. Existencia y Cotas Cuantitativas

• Se establece una cota inferior cuantitativa para el número de parámetros "buenos" $a \in \mathbb{F}_{2^m}^*$. Si $d = q^2 + q + 1$, el número de tales valores es al menos:
  $$\frac{2^m + 1 - (d-1)(d-2)2^{m/2} - d}{d}$$
• Caso Binario ($q=2$): Se prueba que $a=1$ es un parámetro "bueno" siempre que $7 \nmid m$, recuperando así la familia original de Li-Kaleyski. Sin embargo, el trabajo demuestra que existen muchos otros valores de $a$ que también funcionan.

C. Resultados de No-Equivalencia (Innovación)

• No-equivalencia Diagonal con Representantes de Li-Kaleyski:
  $G_a$ es diagonalmente equivalente al representante original $G_1$ si y solo si $a^{q^2+q+1} = 1$.
  • Implicación: Cuando $q=2$ y $7 \nmid m$, el único valor que satisface esto es $a=1$. Por lo tanto, cualquier otro parámetro bueno $a \neq 1$ genera una permutación APN que es CCZ-inequivalente a las conocidas anteriormente.
• No-equivalencia Mutua entre Familias:
  Para $m > 4, m \neq 6$ y $7 \nmid m$, ningún miembro de la familia $G_a$ es CCZ-equivalente a ningún miembro de la familia $H_b$ (para el mismo $q$). Esto confirma que las dos familias proporcionan fuentes genuinamente nuevas y mutuamente inequivalentes de permutaciones APN.

4. Significado e Impacto

1. Expansión del Conocimiento: El artículo resuelve el problema de la existencia de permutaciones APN en una clase más amplia de dimensiones y parámetros, pasando de coeficientes fijos en $\mathbb{F}_2$ a coeficientes en todo $\mathbb{F}_{2^m}$.
2. Nuevas Familias Infinitas: Proporciona dos familias infinitas de permutaciones APN que son esencialmente nuevas (no equivalentes a las conocidas bajo transformaciones CCZ), lo cual es crucial para la criptografía, ya que la diversidad de S-boxes ayuda a resistir ataques de análisis algebraico y diferencial.
3. Reducción de Complejidad: Logra reducir un problema complejo de permutación y APN en tres variables a un problema de exclusión de raíces en un polinomio univariable, simplificando enormemente el análisis y la verificación computacional.
4. Herramientas Teóricas: La aplicación rigurosa de la geometría algebraica (curvas absolutamente irreducibles, límites de Hasse-Weil) para contar parámetros válidos ofrece un marco metodológico robusto para futuros estudios en funciones sobre campos finitos.

5. Problemas Abiertos

Los autores concluyen planteando varias direcciones futuras:

• Encontrar una caracterización algebraica explícita de los parámetros "buenos" cuando $7 \mid m$ (donde $a=1$ falla).
• Investigar si las permutaciones encontradas computacionalmente para $m=3$ se extienden a familias infinitas para $m$ mayores.
• Extender estos resultados a dimensiones pares ($m$ par), donde el criterio de rastreo actual falla.
• Generalizar estas construcciones a funciones con $n > 3$ variables.

En resumen, este trabajo representa un avance significativo en la teoría de funciones APN, proporcionando no solo nuevas construcciones, sino también una comprensión profunda de su estructura algebraica y sus relaciones de equivalencia.