On Generalizations of Maiorana-McFarland and $\mathcal{PS}_{ap}$ Functions

Aquí presento un resumen técnico detallado del artículo "On Generalizations of Maiorana–McFarland and PSap Functions" (Sobre Generalizaciones de las Funciones de Maiorana–McFarland y PSap), estructurado según los puntos solicitados.

1. Problema y Contexto

El artículo aborda un problema fundamental en la teoría de funciones booleanas y su aplicación en criptografía: la construcción y clasificación de funciones bent (funciones booleanas con no linealidad máxima).

• Contexto: Las funciones bent son cruciales para el diseño de cifradores resistentes a ataques de correlación y diferenciales. Existen dos construcciones primarias clásicas: la clase Maiorana–McFarland (MM) y la clase de dispersiones parciales (PSap), específicamente la subclase Desarguesiana.
• El Desafío: Se sabe que la clase completada de Maiorana–McFarland ($MM^\#$) contiene la gran mayoría de las funciones bent conocidas en dimensiones bajas, pero representa una fracción insignificante de todas las funciones bent en dimensiones altas (por ejemplo, en dimensión 8).
• La Pregunta de Investigación: ¿Es posible construir nuevas familias de funciones bent que no sean equivalentes (bajo equivalencia afín extendida, EA) a ninguna función en las clases completadas $MM^\#$ o $PS_{ap}^\#$? Además, ¿cómo se comportan las generalizaciones de estas clases en términos de descomposición y construcción secundaria?

2. Metodología

Los autores emplean un enfoque híbrido que combina teoría de funciones booleanas, teoría de cuerpos finitos y geometría algebraica:

• Criterio de Dillon: Utilizan el criterio basado en derivadas de segundo orden para caracterizar la pertenencia a la clase $MM^\#$. Una función bent pertenece a $MM^\#$ si y solo si posee un subespacio $M$ de dimensión $n/2$ donde las derivadas de segundo orden se anulan idénticamente.
• Análisis de Derivadas de Segundo Orden: Analizan el comportamiento de las derivadas de segundo orden bajo transformaciones de equivalencia afín extendida (EA) para determinar si nuevas construcciones caen fuera de las clases conocidas.
• Teoría de Curvas Algebraicas y Campos de Funciones: Para estudiar la descomposición de las funciones generalizadas $PS_{ap}$, modelan los problemas de existencia de ciertas propiedades (como la constancia de derivadas) como la existencia de puntos racionales afines en curvas algebraicas sobre cuerpos finitos (curvas de Artin-Schreier).
• Acotación de Puntos Racionales: Aplican la Fórmula de Género de Hurwitz y el Límite de Hasse-Weil para demostrar que, bajo ciertas condiciones de grado y tamaño del cuerpo, las curvas asociadas tienen puntos racionales, lo que implica que las derivadas no son constantes.

3. Contribuciones Clave y Resultados

A. Construcción de Funciones Generalizadas Maiorana–McFarland (GMM) fuera de $MM^\#$

• Objetivo: Construir funciones en la clase GMM que no pertenezcan a la clase completada $MM^\#$.
• Método: Los autores proponen una construcción que combina funciones MM que no comparten un subespacio $M$ común de dimensión $n/2$. Específicamente, utilizan una permutación $\pi$ que satisface una propiedad (P) única: el subespacio $M$ de dimensión $n/2$ es único y contiene todos los subespacios $M$ no triviales.
• Resultado Principal (Teorema 1 y Corolarios 7 y 9): Demuestran que si se combinan funciones MM basadas en permutaciones específicas (como la inversa multiplicativa $x^{2^m-2}$ o funciones de Gold $x^{2^k+1}$ bajo ciertas condiciones de $m$ y $k$) dentro del marco GMM, se obtienen funciones bent que tienen un índice de linealidad estrictamente menor que $n/2 + k$.
• Implicación: Estas funciones están fuera de la clase $MM^\#$. Además, debido a su grado algebraico, también están fuera de la clase $PS_{ap}^\#$.

B. Descomposición de Funciones Generalizadas PSap

• Objetivo: Investigar si las funciones generalizadas $PS_{ap}$ admiten una descomposición en funciones bent o semibent mediante concatenación (construcciones secundarias).
• Método: Analizan la dualidad de las funciones $PS_{ap}$ generalizadas. Utilizan el hecho de que una función admite una descomposición semibent si y solo si su dual tiene un subespacio $M$ no trivial.
• Resultado Principal (Proposición 12 y Teorema 2): Demuestran que, cuando el grado del polinomio permutador es suficientemente pequeño en relación con el tamaño del cuerpo finito ($m$), las funciones generalizadas $PS_{ap}$ no admiten descomposición bent ni semibent.
• Técnica: La prueba se basa en demostrar que la derivada de segundo orden de la función dual no es constante, lo cual se logra mostrando que ciertas curvas algebraicas definidas por la estructura de la función tienen puntos racionales (usando el Límite de Hasse-Weil).
• Conclusión: Estas funciones no pueden obtenerse a partir de construcciones secundarias conocidas basadas en la concatenación de funciones bent o semibent.

C. Nueva Construcción Secundaria

• Objetivo: Presentar una construcción secundaria de funciones bent basada en la concatenación de componentes de funciones vectoriales generalizadas $PS_{ap}$.
• Resultado (Teorema 3 y 4): Aprovechando la propiedad de que las componentes de una función vectorial $PS_{ap}$ satisfacen una relación lineal específica en sus duales, los autores construyen nuevas funciones bent booleanas.
• Mecanismo: Definen una función $f$ como una concatenación de componentes de una función vectorial $PS_{ap}$ generalizada, asegurando que la condición necesaria y suficiente para que la concatenación sea bent (la suma de las duales sea igual a 1) se cumpla.

4. Significado e Impacto

• Expansión del Conocimiento: El trabajo proporciona las primeras familias explícitas de funciones bent que están fuera de las clases completadas $MM^\#$ y $PS_{ap}^\#$, llenando un vacío en la clasificación de funciones bent en dimensiones medias y altas.
• Limitación de Construcciones Secundarias: Al demostrar que ciertas funciones $PS_{ap}$ generalizadas no admiten descomposición, el artículo establece límites teóricos sobre qué funciones pueden generarse mediante métodos de concatenación estándar, sugiriendo la necesidad de nuevas técnicas de construcción.
• Herramientas Matemáticas: El uso de curvas algebraicas y campos de funciones para analizar propiedades de funciones booleanas (como la constancia de derivadas) refuerza la conexión profunda entre la teoría de números/algebraica y la criptografía.
• Aplicaciones Criptográficas: La generación de nuevas clases de funciones bent con propiedades de no linealidad y estructura de subespacios diferentes es vital para diseñar cifradores más robustos contra ataques algebraicos y de correlación.

En resumen, el artículo avanza significativamente en la comprensión de la estructura de las funciones bent, ofreciendo nuevas construcciones primarias fuera de las clases clásicas y caracterizando las limitaciones de las construcciones secundarias para estas nuevas familias.