Triprojective almost perfect nonlinear permutations and functions

Resumen Técnico: Permutaciones y Funciones Casi Perfectamente No Lineales Triproyectivas

Enunciado del Problema
El artículo aborda la existencia y construcción de permutaciones Casi Perfectamente No Lineales (APN) sobre espacios vectoriales finitos de dimensión par. En el contexto del criptoanálisis diferencial, las funciones APN (aquellas con uniformidad diferencial $\Delta_F = 2$) son críticas para el diseño de cajas de sustitución (S-Boxes) seguras en redes de sustitución-permutación. Si bien se sabe que las funciones APN existen para dimensiones impares, la existencia de permutaciones APN (biyecciones) para dimensiones pares $n > 6$ sigue siendo un problema abierto mayor. Específicamente, los autores se centran en la construcción de grandes familias de tales funciones en dimensiones $n = 3m$ (donde $m$ es impar) y en la caracterización de sus propiedades, incluidas sus clases de equivalencia y los tamaños de sus conjuntos imagen.

Metodología
Los autores emplean un enfoque estructural basado en aplicaciones "triproyectivas" y "semicuaadráticas". La metodología procede a través de los siguientes pasos:

1. Estructura Proyectiva: Los autores definen una clase de funciones $F \in SQH(3, q)$ (homogéneas semicuaadráticas) sobre $\mathbb{F}_q^3$ (donde $q=2^m$). Estas funciones son inducidas por formas semicuaadráticas que satisfacen propiedades específicas de homogeneidad, lo que les permite inducir aplicaciones bien definidas en el espacio proyectivo $\mathbb{P}^2(\mathbb{F}_q)$.
2. Criterios de Biyección: Basándose en trabajos anteriores (Teorema 1.2), el artículo utiliza una condición sobre un polinomio univariado específico $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ para asegurar que la aplicación inducida en el espacio proyectivo sea una biyección.
3. Análisis de Uniformidad Diferencial:
   • Caso $m/d$ es par: Los autores utilizan el concepto de "núcleo" de la función (un subcuerpo sobre el cual el mapa derivado es lineal) para demostrar que la uniformidad diferencial es $2d$, donde $d = \gcd(k, m)$.
   • Caso $m/d$ es impar: Los autores introducen herramientas de la teoría de anillos de polinomios torcidos (anillos de Ore) $\mathbb{F}_q[t; \sigma]$. Establecen una conexión entre las raíces del polinomio $P(X)$ y la existencia de divisores lineales derechos en el anillo torcido. Mediante la extensión del cuerpo y el análisis del mínimo común múltiplo izquierdo (lclm) de polinomios, demuestran que la uniformidad diferencial permanece en $2d$ incluso en este caso más complejo.
4. Equivalencia y Clasificación: El artículo compara la nueva familia con funciones APN trivariadas existentes (específicamente las de Li-Kaleyski y Bartoli-Stanica) utilizando la equivalencia lineal. Además, demuestra la inequivalencia con las funciones APN de Gold ($x^{2^i+1}$) analizando los grupos de automorfismos lineales ($Aut_L(F)$) y mostrando que no pueden ser conjugados en el grupo lineal general.

Contribuciones y Resultados Clave

• Construcción de Permutaciones APN: El artículo presenta una gran familia de permutaciones APN para espacios vectoriales finitos de dimensión $n=3m$ donde $m$ es impar. Las funciones se definen como:
  $$F(x, y, z) = (x^{\sigma+1} + ay^\sigma z + bx^\sigma y + cx^\sigma z, \quad ay^{\sigma+1} + z^\sigma x + bz^\sigma y + cx^\sigma y, \quad z^{\sigma+1} + x^\sigma y)$$
  donde $\sigma = 2^k$, $a, b, c \in \mathbb{F}_q$, y $a \neq 0$.
• Uniformidad Diferencial: Los autores demuestran que si la ecuación polinómica $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$ no tiene solución en $\mathbb{F}_q$, la uniformidad diferencial de $F$ es $2d$ (donde $d = \gcd(k, m)$). En consecuencia, cuando $d=1$ y $m$ es impar, $F$ es una permutación APN.
• Tamaño del Conjunto Imagen: El artículo caracteriza el tamaño del conjunto imagen de estas funciones. Si $m/d$ es par, la función es $(2d+1)$-a-uno en $\mathbb{F}_q^3 \setminus \{0\}$. Si $m/d$ es impar, la función es biyectiva en $\mathbb{F}_q^3$.
• Unificación de Familias Existentes: Los autores demuestran que varias familias recientemente descubiertas de funciones APN trivariadas (Li-Kaleyski y Bartoli-Stanica) son linealmente equivalentes a instancias específicas de su familia propuesta (obtenidas fijando parámetros específicos $a, b, c$). Esto proporciona una explicación unificada y elemental para estas construcciones, evitando las complejas distinciones de casos y los cálculos de resultantes asistidos por computadora utilizados en pruebas anteriores.
• Inequivalencia con Funciones de Gold: El artículo demuestra que para $m > 2$ y $m \neq 6$, las funciones APN construidas son CCZ-inequivalentes a las funciones APN de Gold. Esto se establece mostrando que sus grupos de automorfismos lineales no son conjugados en $GL(3m, 2)$.

Significado y Afirmaciones
El artículo afirma proporcionar una "gran familia" de permutaciones APN en cada dimensión impar divisible por tres, abordando la pregunta abierta sobre las biyecciones APN para dimensiones pares. El significado radica en:

1. Generalidad: La construcción produce, de manera demostrable, cantidades exponenciales de funciones APN mutuamente inequivalentes dentro de la clase de aplicaciones multiproyectivas.
2. Simplificación: Las pruebas se describen como "libres de computadoras, mucho más cortas y puramente elementales" en comparación con trabajos anteriores, ofreciendo un marco unificado para comprender diversas funciones APN trivariadas.
3. Nuevos Ejemplos: Se muestra que la familia contiene ejemplos que son inequivalentes a funciones APN conocidas (incluidas las funciones de Gold), expandiendo el panorama conocido de primitivas criptográficas.

Los autores señalan que, si bien los espectros de Walsh son conocidos para el caso donde $m/d$ es par, determinar el espectro de Walsh para las permutaciones APN (donde $m$ es impar) sigue siendo un problema abierto. También identifican la clasificación de funciones homogéneas semicuaadráticas que conducen a biyecciones proyectivas como una dirección natural para futuras investigaciones.