On the Walsh spectra of quadratic APN functions

Resumen Técnico: Sobre los Espectros de Walsh de Funciones APN Cuadráticas

Planteamiento del Problema
Las funciones No Lineales Casi Perfectas (APN) son componentes críticos en los sistemas criptográficos simétricos, proporcionando una resistencia óptima contra ataques diferenciales. Una propiedad fundamental de estas funciones es su linealidad, la cual se determina mediante su espectro de Walsh. Si bien la distribución de amplitudes (y, por tanto, el espectro de Walsh) de las funciones APN cuadráticas está completamente caracterizada para dimensiones impares $n$, el caso para $n$ par permanece en gran medida abierto. La única restricción general conocida para $n$ par se deriva del cuarto momento de la transformada de Walsh. Este artículo aborda la brecha en la comprensión de los posibles espectros de Walsh de las funciones APN cuadráticas $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ donde $n$ es par, buscando específicamente derivar condiciones más fuertes sobre sus distribuciones de amplitudes.

Metodología
Los autores establecen dos conexiones geométricas novedosas entre las funciones APN cuadráticas y la geometría finita:

1. Particiones de Espacio Vectorial: El artículo demuestra que la distribución de amplitudes de una función APN cuadrática corresponde de manera única a una partición de espacio vectorial del espacio ambiente $\mathbb{F}_2^n$. Específicamente, las funciones componentes no triviales no plegadas (non-bent) de $F$ se asocian con subespacios en una partición donde la dimensión de cada subespacio está directamente vinculada a la amplitud de la función componente correspondiente.
2. Conjuntos de Bloqueo: El conjunto de componentes no triviales no plegadas, denotado $N_F$, se muestra que forma un tipo específico de conjunto de bloqueo en el espacio proyectivo $PG(n-1, 2)$. Crucialmente, los autores demuestran que la intersección de $N_F$ con cualquier subespacio de dimensión $n/2$ debe contener un número impar de puntos.

Aprovechando teoremas establecidos sobre particiones de espacio vectorial y conjuntos de bloqueo (específicamente resultados sobre las "colas" de las particiones y los conjuntos de bloqueo mínimos), los autores traducen estas restricciones geométricas en límites algebraicos sobre las distribuciones de amplitudes de las funciones APN cuadráticas.

Contribuciones y Resultados Clave

• Conexión con Particiones de Espacio Vectorial (Sección II):

  • El Teorema II.4 establece que si una función componente $F_b$ tiene una amplitud de $2^{(n+k)/2}$, corresponde a un subespacio de dimensión $k$ en una partición de espacio vectorial de $\mathbb{F}_2^n$.
  • Esta conexión permite la aplicación de condiciones de empaquetamiento y límites de dimensión provenientes de la teoría de particiones.
  • Teorema II.10: Una función APN cuadrática puede tener como máximo una función componente con una amplitud mayor que $2^{3n/4}$. Si existe tal componente, todas las demás deben tener una amplitud de al menos $2^{(2n-l)/2}$, donde $l$ es el exponente de la amplitud máxima.
  • Proposiciones II.14–II.16: Se derivan nuevos límites inferiores sobre el número de componentes no plegadas ($|N_F|$) basados en la linealidad y la presencia de amplitudes específicas.

• Conexión con Conjuntos de Bloqueo (Sección III):

  • Corolario III.3: El conjunto $N_F$ es un conjunto de bloqueo en $PG(n-1, 2)$ con respecto a los espacios $(n/2)$, con la propiedad adicional de que cada uno de dichos espacios interseca a $N_F$ en un número impar de puntos.
  • Teorema III.9: Este es el primer límite superior no trivial y general sobre el número de funciones componentes plegadas (bent) para una función APN cuadrática. Específicamente, para $n \ge 6$, el número de componentes no plegadas satisface $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$. La igualdad es posible solo si $n=8$. En consecuencia, el número de componentes plegadas es como máximo $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$.

• Síntesis y Análisis Dimensional (Sección IV):

  • Al combinar las restricciones de particiones y conjuntos de bloqueo, los autores eliminan varias distribuciones de amplitudes teóricamente posibles.
  • Teorema IV.1: Las particiones de espacio vectorial de tipo $[(n/2)^{2^{n/2+1}}]$ (una $(n/2)$-dispersión o spread) no corresponden a ninguna función APN cuadrática.
  • Teorema IV.5: Para $n=8$, el artículo reduce las distribuciones de amplitudes posibles a una lista específica (excluyendo la partición trivial y la 4-dispersión), reduciendo el número de espectros de Walsh extendidos potenciales a un máximo de 18 tipos distintos.
  • Proposición IV.4: El artículo compara la fuerza de los límites inferiores derivados sobre $|N_F|$ a través de diferentes rangos de parámetros, identificando qué límite es dominante dependiendo de la linealidad de la función.

• Equivalencia y Permutaciones (Sección V):

  • El artículo analiza cómo estas estructuras se comportan bajo la equivalencia EA y la equivalencia CCZ.
  • Corolario V.6: Si una función APN cuadrática es CCZ-equivalente a una permutación, no puede tener pocas componentes no plegadas; específicamente, $|N_F| \ge 3(2^{n/2}-1)$, y $N_F$ debe ser un conjunto de bloqueo triple (3-fold blocking set).

Significado y Afirmaciones
El artículo afirma proporcionar las primeras condiciones generales sobre los espectros de Walsh de funciones APN cuadráticas más allá del conocido límite del cuarto momento. Al vincular las propiedades algebraicas de estas funciones con las estructuras combinatorias de las particiones de espacio vectorial y los conjuntos de bloqueo, los autores derivan restricciones fuertes sobre las posibles distribuciones de amplitudes.

Los autores declaran explícitamente que sus resultados:

1. Demuestran que una función APN cuadrática puede tener como máximo una componente con una amplitud mayor que $2^{3n/4}$.
2. Proporcionan el primer límite superior no trivial sobre el número de componentes plegadas.
3. Ofrecen condiciones para determinar si una función es CCZ-equivalente a una permutación basándose en su número de componentes plegadas.
4. Listan sistemáticamente todas las distribuciones de amplitudes posibles para dimensiones pares pequeñas (específicamente $n=6, 8, 10$), destacando cuáles se realizan y cuáles permanecen como problemas abiertos.

El artículo concluye listando problemas abiertos, incluida la existencia de funciones APN con distribuciones de amplitudes específicas en la dimensión 8 y la búsqueda de familias infinitas de funciones APN cuadráticas con espectros de Walsh no clásicos. Los autores mantienen un tono modesto, señalando que, aunque han excluido muchas posibilidades, la clasificación completa de los espectros de Walsh para funciones APN cuadráticas sigue siendo un desafío abierto.