On APN Exponents and the Differential and Boomerang Properties of Binomials in Characteristic 3

Resumen Técnico: Sobre Exponentes APN y las Propiedades Diferencial y Boomerang de Binomios en Característica 3

Planteamiento del Problema
El artículo investiga las propiedades criptográficas de funciones binomiales de la forma $F_r(x) = x^r(1 + \chi(x))$ sobre cuerpos finitos $\mathbb{F}_{3^n}$, donde $\chi(x)$ es el carácter cuadrático. Si bien la uniformidad diferencial es una métrica estándar para la resistencia contra ataques diferenciales, no captura completamente la resistencia a los ataques boomerang. Se introdujo la noción de uniformidad boomerang ($\beta_F$) para abordar esta cuestión. Estudios anteriores [9] establecieron que, para ciertos exponentes $r$, la función $F_r$ exhibe baja uniformidad diferencial y una uniformidad boomerang acotada por 2. Sin embargo, observaciones empíricas sugieren que, en característica 3, los casos de uniformidad boomerang extremadamente baja (específicamente 0 o 1) ocurren con mayor frecuencia que en otras características. El artículo tiene como objetivo analizar sistemáticamente estos fenómenos, identificar los exponentes $r$ específicos que producen uniformidad boomerang 0 o 1, y proporcionar demostraciones rigurosas para estas clases.

Metodología
Los autores emplean una combinación de análisis teórico y verificación computacional:

1. Marco Teórico: El estudio se basa en el concepto de funciones "localmente-PN" y "localmente-APN". Mediante el análisis de la ecuación diferencial $(x+1)^r - x^r = b$ y el sistema boomerang asociado, los autores derivan las condiciones bajo las cuales el espectro diferencial y el espectro boomerang pueden determinarse explícitamente.
2. Clasificación APN: El artículo proporciona una parametrización sistemática de las funciones de potencia No Lineales Casi Perfectas (APN) que surgen de la construcción de Zha y Wang [23]. Esto implica resolver la condición diofántica $(3m+1)r - 2 = k(3^n-1)$ para generar familias explícitas de exponentes.
3. Sumas de Caracteres y Análisis Espectral: Para determinar el espectro boomerang de clases específicas (notablemente $r = 3^n - 3$), los autores evalúan sumas de caracteres que involucran caracteres cuadráticos y raíces de polinomios.
4. Búsqueda Computacional: Se realizaron búsquedas exhaustivas para valores pequeños de $n$ (hasta $n=13$) utilizando SageMath para identificar exponentes que producen uniformidad boomerang 0 o 1. Estos resultados se contrastan con las familias teóricas derivadas.

Contribuciones y Resultados Clave

• Parametrización de Exponentes APN: Los autores presentan una parametrización explícita (Proposición 3.3) para exponentes APN derivados del marco en [23]. Demuestran que, para $n \le 13$, esta construcción generalizada da cuenta de todas las funciones de potencia APN conocidas en característica 3 que no figuraban previamente en tablas estándar [2]. Esto incluye la recuperación de clases conocidas (por ejemplo, $r = 3^{(n+1)/2} - 1$) y la identificación de nuevos casos esporádicos.
• Dos Clases con Uniformidad Boomerang 0: El artículo demuestra rigurosamente que dos clases específicas de binomios $F_r$ poseen la uniformidad boomerang mínima posible de 0:
  1. Exponentes $r$ que surgen de la construcción APN en [23] (satisfaciendo la condición $(3m+1)r - 2 = k(3^n-1)$).
  2. El exponente $r = 2 \cdot 3^{(n-1)/2} + 1$.
     Para ambas clases, los autores demuestran que $F_r$ es localmente-PN y derivan sus espectros diferenciales.
• Análisis de $r = 3^n - 3$: El artículo analiza el binomio con exponente $r = 3^n - 3$. Se demuestra que, para $n$ impar con $n \ge 5$, esta función es localmente-APN con uniformidad boomerang 1. Los autores determinan completamente su espectro boomerang evaluando sumas de caracteres específicas, proporcionando fórmulas explícitas para el número de valores de $b$ que producen $\beta_{F_r}(1, b) = 0$ y $1$.
• Clasificación Numérica: Mediante búsquedas exhaustivas para $n \le 13$, los autores compilan tablas de exponentes que producen uniformidad boomerang 0 y 1. Observan que, para $n \le 9$, la condición de ser localmente-PN parece ser tanto necesaria como suficiente para la uniformidad boomerang 0, incluso sin la suposición estricta $\gcd(r, 3^n-1) \in \{1, 2\}$ utilizada en cotas teóricas anteriores.

Significado
El artículo aclara y extiende los estudios existentes sobre las propiedades criptográficas de binomios en característica 3. Su significado principal radica en:

1. Caracterización Sistemática: Proporcionar un marco unificado que explica por qué ciertos binomios en característica 3 alcanzan uniformidad boomerang 0 o 1, vinculando estas propiedades directamente con construcciones específicas de exponentes APN.
2. Extensión de Cotas: Demostrar que la cota general de uniformidad boomerang 2 (establecida en [9]) puede mejorarse estrictamente a 0 o 1 para familias infinitas específicas en característica 3.
3. Completitud de la Clasificación APN: Mostrar que la parametrización de exponentes APN de [23] cubre todas las funciones de potencia APN conocidas en característica 3 para $n$ pequeño, sugiriendo una estructura comprehensiva para estas funciones.
4. Validación Empírica: Los resultados numéricos respaldan los hallazgos teóricos y destacan una fuerte correlación entre la propiedad localmente-PN y la uniformidad boomerang 0, planteando esta relación como un área potencial para futuras demostraciones rigurosas.

Los autores concluyen que, aunque han identificado familias infinitas y casos esporádicos con propiedades boomerang óptimas, la equivalencia precisa entre la propiedad localmente-PN y la uniformidad boomerang 0 sigue siendo un problema abierto, y extender los casos esporádicos de uniformidad boomerang 1 a familias infinitas es una dirección para futuras investigaciones.