Sobre los espectros de Walsh de funciones APN cuadráticas

Información Básica

• ID del artículo: 2510.12008
• Título: On the Walsh spectra of quadratic APN functions
• Autores: Sophie Hannah Bénéteau (University of Florida), Nicolas Goluboff (University of Massachusetts Amherst), Lukas Kölsch (University of South Florida), Divyesh Vaghasiya (University of South Florida)
• Clasificación: math.CO cs.IT math.IT
• Fecha de publicación: 15 de octubre de 2025 (preimpresión en arXiv)
• Enlace del artículo: https://arxiv.org/abs/2510.12008

Resumen

Las funciones APN (Almost Perfect Nonlinear, casi perfectamente no lineales) desempeñan un papel central en el diseño de cifrados de bloque, siendo funciones óptimas para resistir ataques diferenciales. Una de las propiedades más importantes de las funciones APN es su linealidad, que está directamente relacionada con el espectro de Walsh de la función. Este artículo establece dos conexiones novedosas que permiten derivar condiciones fuertes sobre el espectro de Walsh de funciones APN cuadráticas. El artículo demuestra que la transformada de Walsh de una función APN cuadrática $F$ que opera en $n=2k$ bits está únicamente asociada con una partición del espacio vectorial $\mathbb{F}_2^n$ y con conjuntos de bloqueo específicos en el espacio proyectivo correspondiente $PG(n-1,2)$. Estas conexiones permiten demostrar múltiples resultados sobre el espectro de Walsh de $F$, tales como probar que $F$ puede tener como máximo una función componente con amplitud mayor que $2^{\frac{3}{4}n}$, y encontrar el primer límite superior no trivial para el número de funciones componentes dobladas de funciones APN cuadráticas.

Antecedentes de investigación y motivación

Importancia del problema

1. Aplicaciones criptográficas: Las funciones APN son bloques de construcción fundamentales en el diseño de sistemas criptográficos simétricos, particularmente en redes de sustitución-permutación (SPN) de cifrados de bloque, proporcionando resistencia óptima contra ataques diferenciales.
2. Desafíos teóricos: Aunque la distribución de amplitudes de funciones APN cuadráticas en dimensiones impares ha sido completamente determinada (todas las componentes no triviales tienen amplitud $2^{\frac{n+1}{2}}$), el caso de dimensiones pares sigue siendo un problema abierto.
3. Limitaciones existentes:
   • Para $n$ par, las únicas restricciones conocidas sobre amplitudes provienen de la caracterización del cuarto momento de la transformada de Walsh
   • Falta de límites no triviales sobre el número de funciones componentes dobladas de funciones APN cuadráticas
   • Comprensión insuficiente de la estructura profunda del espectro de Walsh

Motivación de la investigación

Este artículo tiene como objetivo profundizar en la comprensión de las propiedades estructurales del espectro de Walsh de funciones APN cuadráticas mediante el establecimiento de nuevas conexiones entre estas funciones y objetos geométricos (particiones de espacios vectoriales y conjuntos de bloqueo), derivando así condiciones más fuertes.

Contribuciones principales

1. Establecimiento de conexión con particiones de espacios vectoriales: Se demuestra la correspondencia única entre la distribución de amplitudes de una función APN cuadrática $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ ($n$ par) y las particiones del espacio vectorial $\mathbb{F}_2^n$.
2. Construcción de teoría de conjuntos de bloqueo: Se demuestra que el conjunto de funciones componentes no triviales y no dobladas $N_F$ forma un conjunto de bloqueo especial en el espacio proyectivo $PG(n-1,2)$.
3. Derivación de nuevas condiciones restrictivas:
   • Se prueba que $F$ puede tener como máximo una función componente con amplitud mayor que $2^{\frac{3}{4}n}$
   • Se establece el primer límite superior no trivial para el número de funciones componentes dobladas
   • Se proporcionan condiciones necesarias para que la función sea CCZ-equivalente a una permutación
4. Análisis completo de dimensiones pequeñas: Se realiza análisis exhaustivo para dimensiones 6, 8 y 10, determinando todas las distribuciones de amplitudes posibles.

Explicación detallada de métodos

Definición de la tarea

Investigar la estructura del espectro de Walsh de funciones APN cuadráticas $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ ($n$ par), donde:

• Entrada: Función APN cuadrática $F$
• Salida: Condiciones restrictivas y propiedades estructurales del espectro de Walsh
• Objetivo: Comprender las posibilidades y limitaciones de la distribución de amplitudes

Marco teórico fundamental

1. Teoría de particiones de espacios vectoriales

Definición de función diferencial: Para $a \in \mathbb{F}_2^n$ no nulo, se define $D_{F,a}(x) = F(x) + F(x+a)$.

Construcción de espacios vectoriales: Se define

• $T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}$
• $\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}$
• $V_b = T_b \cup \overline{T_b}$

donde $H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}$.

Teorema principal (Teorema 2.4): La amplitud de $F_b$ es $2^{\frac{n+\dim(V_b)}{2}}$.

2. Teoría de conjuntos de bloqueo

Propiedades de conjuntos de bloqueo: El conjunto de funciones componentes no triviales y no dobladas $N_F$ forma un conjunto de bloqueo en $PG(n-1,2)$ con respecto a $(n/2)$-espacios, donde la intersección con cada $(n/2)$-espacio tiene tamaño impar.

Resultado clave: Utilizando el teorema de Govaerts-Storme sobre el tamaño de conjuntos de bloqueo mínimos no triviales, se obtiene un límite superior para el número de funciones componentes dobladas.

Puntos de innovación técnica

1. Método de geometrización: Por primera vez, se transforma el problema del espectro de Walsh de funciones APN cuadráticas en un problema geométrico de particiones de espacios vectoriales y conjuntos de bloqueo.
2. Caracterización estructural: Mediante $\dim(V_b)$ se determina directamente la amplitud de la función componente $F_b$, estableciendo una conexión directa entre la estructura algebraica y las propiedades espectrales.
3. Aplicación interdisciplinaria: Se aplica ingeniosamente la teoría profunda de particiones de espacios vectoriales y conjuntos de bloqueo de la geometría finita.

Configuración experimental

Métodos de verificación teórica

Este artículo es principalmente investigación teórica, verificando resultados mediante:

1. Análisis completo de dimensiones pequeñas:
   • Dimensión 6: Verificación de que todos los tipos de particiones de espacios vectoriales posibles corresponden a funciones APN cuadráticas conocidas
   • Dimensión 8: Determinación de 18 distribuciones de amplitudes posibles
   • Dimensión 10: Análisis de todos los casos teóricamente posibles
2. Verificación de funciones conocidas:
   • Verificación de funciones con espectro de Walsh clásico
   • Análisis de funciones con linealidad máxima
   • Verificación de propiedades de conjuntos de bloqueo de la función $x^3$

Herramientas computacionales

El artículo utiliza verificación asistida por computadora para:

• Enumerar todas las particiones de espacios vectoriales posibles en casos de dimensiones pequeñas
• Verificar la consistencia de resultados teóricos con funciones APN conocidas

Resultados experimentales

Resultados teóricos principales

1. Restricciones de amplitud (Teorema 2.10)

Resultado: Sea $n$ par, $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ una función APN cuadrática con linealidad $L(F) = 2^{\frac{n+l}{2}}$ donde $l > n/2$, entonces:

• $F$ tiene exactamente una función componente con amplitud $2^{\frac{n+l}{2}}$
• Todas las demás componentes tienen amplitud como máximo $2^{\frac{2n-l}{2}}$
• En particular, cualquier función APN cuadrática tiene como máximo una función componente con amplitud mayor que $2^{\frac{3n}{4}}$

2. Límite superior de funciones componentes dobladas (Teorema 3.9)

Resultado: Sea $n \geq 6$ par, $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ una función APN cuadrática, entonces: $|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ donde la igualdad es posible solo cuando $n=8$.

3. Clasificación completa para dimensión 8 (Teorema 4.5)

Para $F: \mathbb{F}_2^8 \to \mathbb{F}_2^8$ función APN cuadrática, las distribuciones de amplitudes posibles son:

• $[0^{190}, 2^{64}, 6^1]$
• $[0^{238-4i}, 2^{5i}, 4^{17-i}]$, donde $1 \leq i \leq 17$

Análisis de ablación

1. Comparación de límites (Proposición 4.4)

Comparación de tres límites inferiores diferentes para $|N_F|$:

• Límite de partición de espacios vectoriales: Más fuerte cuando $k < n/2$
• Límite de conjunto de bloqueo: Más fuerte cuando $k = n/2$
• Límite de dimensión: Más fuerte cuando $k > n/2$

2. Análisis de equivalencia

Se demuestra que bajo equivalencia EA:

• Las particiones de espacios vectoriales preservan la equivalencia (Teorema 5.2)
• Los conjuntos de bloqueo preservan la equivalencia (Teorema 5.1)

Hallazgos importantes

1. Restricciones estructurales: El espectro de Walsh de funciones APN cuadráticas está sujeto a restricciones geométricas estrictas, no siendo arbitrario.
2. Efecto de dimensión: Con el aumento de dimensión, el número de distribuciones de amplitudes posibles disminuye drásticamente.
3. Condiciones de equivalencia CCZ: Si una función cuadrática es CCZ-equivalente a una permutación, entonces $|N_F| \geq 3(2^{n/2} - 1)$.

Trabajo relacionado

Principales direcciones de investigación

1. Clasificación de funciones APN: Trabajo de Carlet, Charpin, Zinoviev y otros
2. Teoría del espectro de Walsh: Método del cuarto momento y límites de linealidad
3. Particiones de espacios vectoriales: Teoría de construcción de Heden, Bu y otros
4. Teoría de conjuntos de bloqueo: Límites óptimos de Govaerts-Storme

Ventajas de este artículo

• Primera conexión directa entre espectro de Walsh y objetos geométricos
• Proporciona restricciones más fuertes que el método clásico del cuarto momento
• Unifica perspectivas algebraicas y geométricas

Conclusiones y discusión

Conclusiones principales

1. El espectro de Walsh de funciones APN cuadráticas posee una estructura geométrica profunda
2. Las particiones de espacios vectoriales y los conjuntos de bloqueo proporcionan herramientas poderosas para comprender el espectro de Walsh
3. La mayoría de las distribuciones de amplitudes teóricamente posibles no pueden realizarse en la práctica

Limitaciones

1. Problemas de construcción: La teoría excluye muchas posibilidades, pero no proporciona nuevos métodos de construcción
2. Restricción de dimensión: Los resultados principales se concentran en dimensiones pares
3. Complejidad computacional: El análisis completo en casos de dimensiones altas sigue siendo difícil

Direcciones futuras

El artículo propone 6 problemas abiertos, incluyendo:

1. Encontrar ejemplos de distribuciones de amplitudes faltantes en dimensión 8
2. Mejorar los límites de $|N_F|$
3. Encontrar más tipos de particiones de espacios vectoriales no realizables

Evaluación profunda

Fortalezas

1. Innovación teórica: Establece una perspectiva geométrica completamente nueva para comprender el espectro de Walsh
2. Sistematicidad del método: Investigación sistemática desde dos ángulos: particiones de espacios vectoriales y conjuntos de bloqueo
3. Profundidad de resultados: Obtiene múltiples límites no triviales por primera vez
4. Completitud del análisis: Análisis exhaustivo de casos de dimensiones pequeñas

Insuficiencias

1. Falta de construcción: Principalmente resultados de exclusión, carece de nuevas construcciones de funciones APN
2. Verificación computacional: Algunos resultados dependen de verificación por computadora, las pruebas teóricas no son completamente exhaustivas
3. Limitaciones de aplicación: Principalmente contribuciones teóricas, el valor de aplicación en criptografía práctica requiere verificación

Impacto

1. Valor académico: Proporciona nuevas herramientas y perspectivas de investigación para la teoría de funciones APN
2. Contribución metodológica: El método de geometrización puede inspirar investigaciones sobre otros problemas criptográficos
3. Problemas abiertos: Los problemas propuestos señalan direcciones para investigaciones posteriores

Escenarios de aplicación

• Análisis teórico de funciones APN cuadráticas
• Diseño y análisis de cajas S en criptografía
• Investigación de aplicaciones de geometría finita en criptografía
• Investigación de la estructura del espectro de Walsh de funciones booleanas

Referencias bibliográficas

El artículo cita 25 referencias importantes que abarcan múltiples campos como teoría de funciones APN, particiones de espacios vectoriales, teoría de conjuntos de bloqueo y otros, reflejando las características de la investigación interdisciplinaria. Las referencias clave incluyen la monografía sobre funciones booleanas de Carlet, el trabajo sobre conjuntos de bloqueo de Govaerts-Storme, y la investigación sobre particiones de espacios vectoriales de Heden y otros.