🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

Este artículo analiza los resultados fundamentales y los avances recientes en el diseño y análisis de las funciones booleanas bent, centrándose específicamente en su relación con la clase de Maiorana-McFarland completada.

Autores originales: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Publicado 2026-08-25

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En la arquitectura oculta de la seguridad digital moderna, existe un tipo especial de objeto matemático conocido como función bent. Estas no son dispositivos físicos ni entidades biológicas, sino reglas complejas para procesar datos binarios—cadenas de unos y ceros que forman la base de toda la comunicación informática. Imagine un vasto paisaje de reglas posibles, donde la mayoría son predecibles y fáciles de analizar. Las funciones bent se sitúan en la cima misma de la imprevisibilidad, alejándose tanto como sea posible de cualquier patrón lineal simple. Debido a esta extrema irregularidad, son herramientas invaluables para proteger los datos en la criptografía y en los códigos de corrección de errores, actuando como el ruido caótico que impide que los fisgadores encuentren una señal. Durante décadas, los matemáticos han sabido cómo construir una familia específica y bien comprendida de estas funciones, un grupo nombrado tras los investigadores que las describieron por primera vez. Esta familia, a menudo llamada la clase Maiorana-McFarland, ha servido como el plano principal para la creación de funciones bent, de forma muy similar a un plano arquitectónico estándar para construir una casa. Sin embargo, una pregunta persistente ha rondado el campo: ¿son estos planos estándar la única forma de construir tales funciones, o existen otros diseños más extraños que aún no hemos descubierto?

Un equipo de investigadores ha realizado ahora un examen exhaustivo de esta cuestión, analizando todo el paisaje de las funciones bent para ver cómo se relacionan con esa familia estándar. Su trabajo confirma que los planos conocidos, aunque útiles, representan solo una fracción minúscula del total de las posibilidades. En el caso específico de las funciones con ocho variables, las búsquedas computacionales han revelado que el número total de funciones bent es astronómicamente grande, aproximadamente dos a la potencia de cien y seis. En marcado contraste, se estima que el número de funciones que pueden construirse utilizando el plano estándar de Maiorana-McFarland es, como máximo, dos a la potencia de ochenta y uno. Esta enorme brecha sugiere que la gran mayoría de las funciones bent son fundamentalmente diferentes de aquellas que hemos sido capaces de construir explícitamente. El objetivo de los investigadores era mapear el territorio entre estos dos extremos, identificando nuevos métodos para construir funciones bent que definitivamente no encajen en el molde antiguo y comprendiendo las razones estructurales de por qué son tan diferentes.

El artículo comienza examinando dos familias específicas de funciones bent, conocidas como las clases C y D, que fueron diseñadas para modificar el plano estándar. Estas familias introducen cambios pequeños y deliberados al esquema estándar, añadiendo patrones específicos a la salida. Los investigadores investigaron si estas modificaciones eran suficientes para empujar las funciones resultantes fuera de la familia estándar. Encontraron que, bajo ciertas condiciones, estas funciones modificadas son, de hecho, distintas. Por ejemplo, si la permutación subyacente utilizada en la construcción posee propiedades algebraicas específicas—esencialmente, si carece de ciertas simetrías ocultas—la función bent resultante no puede ser transformada de nuevo a la forma estándar. Los autores proporcionaron reglas claras y comprobables para determinar cuándo una función pertenece a estas nuevas y exóticas familias y cuándo permanece atrapada dentro de la antigua. También exploraron las "superclases", que combinan diferentes tipos de modificaciones, descubriendo que mientras algunas combinaciones funcionan, otras no logran producir funciones bent, revelando el delicado equilibrio requerido para mantener el nivel de imprevisibilidad necesario.

Más allá de estas familias específicas, los investigadores observaron funciones construidas utilizando la estructura multiplicativa de los cuerpos finitos, a menudo descritas mediante términos de traza. Estas son funciones donde la salida depende de la suma de un número elevado a una potencia específica. El estudio destaca que muchas de estas funciones, particularmente aquellas basadas en ciertos exponentes, están demostrablemente fuera de la familia estándar. Los investigadores utilizaron una prueba matemática específica que involucra derivadas de segundo orden—una forma de medir cómo el cambio de la tasa de cambio de la función en sí mismo cambia—para probar que estas funciones carecen de la regularidad estructural encontrada en la clase estándar. También examinaron funciones que actúan como indicadores de otros objetos matemáticos importantes, como las funciones casi perfectamente no lineales, mostrando que estos indicadores suelen poseer las propiedades únicas y no estándar de las funciones bent que se encuentran fuera de las familias conocidas.

Un tema central de la investigación es el concepto de un "índice de linealidad", que puede pensarse como una medida de cuánto se asemeja una función a un patrón lineal simple. Las funciones Maiorana-McFarland estándar tienen un índice de linealidad alto, lo que significa que pueden descomponerse en grandes piezas afines simples. Los investigadores identificaron una nueva categoría de funciones con el índice de linealidad mínimo posible, que llaman "óptimas". Estas funciones son lo opuesto a las estándar; son tan irregulares que no pueden simplificarse en bloques afines de gran tamaño en absoluto. El artículo detalla cómo construir estas funciones óptimas y demuestra que son fundamentalmente diferentes de la clase estándar. Al estudiar los "subespacios-M"—subestructuras geométricas especiales dentro del dominio de la función que revelan su simetría subyacente—los autores mostraron que estas funciones óptimas poseen una estructura única y mínima que las funciones estándar simplemente no poseen.

La encuesta también se adentra en un marco más amplio y flexible llamado la clase Maiorana-McFarland generalizada. Este marco permite funciones que se construyen a partir de piezas afines de tamaños variables, en lugar del tamaño fijo utilizado en la clase estándar. Los investigadores caracterizaron exactamente cuándo una función en esta clase más amplia permanece dentro de la familia estándar y cuándo se sale de ella. Encontraron que, mediante la elección cuidadosa de los bloques de construcción, se pueden crear funciones que son "casi" estándar pero aun así distintas, así como funciones que son completamente ajenas a la familia estándar. El artículo concluye enumerando varios problemas abiertos, reconociendo que, aunque han mapeado porciones significativas de este territorio matemático, la enumeración completa de todas las funciones bent sigue siendo un misterio. Desafían a los futuros investigadores a encontrar más familias infinitas de estas funciones exóticas y a comprender las estructuras algebraicas precisas que las hacen únicas, asegurando que el campo continúe evolucionando más allá de las limitaciones de los planos originales.

Resumen Técnico: Funciones Bent y la Clase Maiorana-McFarland Completada

Planteamiento del Problema
Las funciones booleanas bent, introducidas por Rothaus, representan una clase fundamental de funciones en un número par de variables que alcanzan la no linealidad máxima (distancia máxima de las funciones afines). Si bien la clase Maiorana-McFarland (M) y su versión completada ( $M^\#$ ) constituyen la familia de funciones bent explícitas más exhaustivamente comprendidas, la evidencia computacional reciente indica una discrepancia significativa entre el número total de funciones bent y aquellas que pertenecen a $M^\#$ . Específicamente, en dimensión 8, el número total de funciones bent es aproximadamente $2^{106}$ , mientras que el número de funciones equivalentes a Maiorana-McFarland se estima en, como máximo, $2^{81}$ . Esta observación motiva el problema central de este estudio: caracterizar las funciones bent que se encuentran fuera de la clase Maiorana-McFarland completada ( $M^\#$ ), comprender sus estructuras algebraicas y desarrollar métodos de construcción explícitos para tales funciones. El artículo se centra en el "problema de exclusión": determinar la intersección de diversas clases de funciones bent con $M^\#$ e identificar las condiciones bajo las cuales las funciones están demostrablemente fuera de esta clase.

Metodología
El artículo emplea una metodología de encuesta exhaustiva, sintetizando resultados fundamentales y avances recientes en el diseño y análisis de funciones booleanas bent. El enfoque técnico se basa fuertemente en:

Caracterización Algebraica: Utilizando el criterio de la derivada de segundo orden (Lema 1.2) para caracterizar la pertenencia a $M^\#$ . Una función pertenece a $M^\#$ si y solo si existe un subespacio $U$ de dimensión $m$ tal que todas las derivadas de segundo orden $D_a D_b f$ se anulan para $a, b \in U$ .
Índice de Linealidad y Subespacios M: Analizando el "índice de linealidad" ($ind(f)$), definido como la dimensión máxima de un subespacio M (un subespacio donde las derivadas de segundo orden se anulan). Las funciones con $ind(f) = n/2$ pertenecen a $M^\#$ , mientras que aquellas con índices mínimos ($ind(f)=1$) se denominan $\ell$ -óptimas.
Construcciones Secundarias: Investigando cómo las operaciones como las sumas directa/indirecta, las concatenaciones (2- y 4-concatenación) y la adición de términos de traza o indicadores de subespacios afectan la pertenencia a $M^\#$ .
Marcos Generalizados: Extendiendo el análisis desde la clase clásica $M$ ( $r=s=n/2$ ) hacia la clase Maiorana-McFarland Generalizada (GMM) ( $Mr,s$ ), donde $f(x,y) = x \cdot \phi(y) + h(y)$ con $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s$ y $r \neq s$ .

Contribuciones Clave y Resultados

Clases C y D de Carlet: El artículo detalla las clases C y D, que modifican la forma Maiorana-McFarland añadiendo indicadores de subespacios vectoriales.
- Clase C: Funciones de la forma $x \cdot \pi(y) + 1_{L^\perp}(x)$ . Los autores resumen las condiciones suficientes sobre la permutación $\pi$ y el subespacio $L$ (específicamente la propiedad (C)) que garantizan que la función sea bent y esté fuera de $M^\#$ . Un resultado clave involucra permutaciones cuyas componentes carecen de estructuras lineales no nulas.
- Clase D y $D_0$ : Funciones de la forma $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ y la subclase $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ ). El artículo proporciona una caracterización completa de $D_0 \cap M^\#$ , mostrando que para permutaciones cuadráticas, la pertenencia depende de si la permutación es afín en un hiperplano afín. Para grados superiores, las funciones suelen estar fuera de $M^\#$ .
- Superclases: La encuesta examina las superclases (SC, CD, SD) formadas por la combinación de indicadores. Identifica que, mientras algunas combinaciones (como SC) producen funciones bent fuera de $M^\#$ , otras (como SD) no logran producir funciones bent en absoluto.
Términos de Traza y la Propiedad $P_\tau$ :
- El artículo revisa funciones bent monómicas, binomiales y relacionadas definidas mediante términos de traza (por ejemplo, exponentes de Dillon y Kasami). Confirma que muchas de estas, particularmente aquellas con exponentes Niho específicos, se encuentran fuera de $M^\#$ .
- Una parte significativa se dedica a la propiedad $P_\tau$ , que implica añadir combinaciones polinómicas de términos de traza a una función bent. El artículo detalla cómo la propiedad $P_\tau$ , caracterizada por la anulación de las derivadas de segundo orden de la función dual, permite la construcción de familias infinitas de funciones bent fuera de $M^\#$ que no están cubiertas por las clases C o D.
Clase Maiorana-McFarland Generalizada (GMM):
- El artículo introduce la clase GMM ( $Mr,s$ ) y su versión completada. Caracteriza la naturaleza bent en esta clase utilizando "conjuntos bent" y "funciones bent parcialmente definidas".
- Casi Maiorana-McFarland ( $k=1$ ): Se analizan las funciones con índice de linealidad $n/2 - 1$ . El artículo distingue entre particiones "triviales", "no apropiadas" y "propias" del dominio, mostrando que ciertas particiones propias producen funciones bent fuera de $M^\#$ .
- Funciones $\ell$ -óptimas: La encuesta analiza las funciones con el índice de linealidad mínimo ($ind(f)=1$), señalando que estas son lo "opuesto" a las funciones Maiorana-McFarland. Se destacan las construcciones que involucran permutaciones con la propiedad (P1) (derivadas de segundo orden no nulas) como un método para generar tales funciones.
Subespacios M y Construcciones Secundarias:
- El artículo proporciona un análisis algebraico y combinatorio profundo de los subespacios M. Establece límites para el número de subespacios M máximos y vincula la clasificación de las funciones bent.
- Presenta condiciones necesarias y suficientes para que las construcciones secundarias (suma directa, suma indirecta, 2- y 4-concatenación) resulten en funciones fuera de $M^\#$ . Notablemente, demuestra que la 4-concatenación de una función bent fuera de $M^\#$ con una función bent arbitraria produce una nueva función bent fuera de $M^\#$ .

Significado
El artículo se posiciona como una encuesta exhaustiva que cierra la brecha entre la clase Maiorana-McFarland, bien comprendida, y el vasto espacio, en gran parte no clasificado, de las funciones bent. Su significado principal radica en:

Sistematizar la Exclusión: Proporcionar un marco unificado para determinar cuándo las funciones bent caen fuera de $M^\#$ , yendo más allá de ejemplos ad hoc hacia caracterizaciones estructurales basadas en índices de linealidad y subespacios M.
Expandir los Métodos de Construcción: Detallar métodos explícitos (C, D, $P_\tau$ , GMM) para generar familias infinitas de funciones bent fuera de $M^\#$ , abordando la escasez de ejemplos conocidos en dimensiones fijas.
Clarificar la Estructura Algebraica: Introducir y refinar conceptos como el índice de linealidad y los subespacios M como herramientas fundamentales para comprender las propiedades algebraicas de las funciones bent y su relación con la jerarquía generalizada de Maior-McFarland.
Identificar Problemas Abiertos: El artículo concluye enumerando numerosos problemas abiertos, incluyendo la enumeración exacta de las clases de equivalencia EA en $M^\#$ , la extensión de estas teorías a las funciones bent $p$ -arias, y la construcción de conjuntos de diferencia fuera de la clase de McFarland.

Los autores mantienen un tono modesto, reconociendo que, si bien se ha progresado significativamente en la identificación de funciones fuera de $M^\#$ , la enumeración total de las funciones bent y una clasificación completa de sus estructuras algebraicas siguen siendo desafíos abiertos. El trabajo sirve como una referencia fundamental para investigadores que buscan diseñar funciones booleanas con propiedades de no linealidad específicas que no pueden ser capturadas por la construcción estándar de Maiorana-McFarland.

Más como este