Sobre algunas construcciones de funciones Bent

Abstract

Las funciones booleanas juegan un papel muy importante en la criptografía moderna y son la pieza fundamental de numerosos criptosistemas gracias a su habilidad para proporcionar seguridad en las comunicaciones. El estudio de las funciones booleanas, tanto desde una perspectiva teórica como práctica, es crucial en la provisión de seguridad en las aplicaciones criptográficas como los cifradores en bloque, los cifradores en flujo y las funciones hash. Las propiedades de no linealidad y equilibrio son dos criterios esenciales criptográficamente para las funciones booleanas. La no linealidad es la propiedad más importante en cualquier criptosistema de clave simétrica para alcanzar confusión. La definición más usada de no linealidad es la mínima distancia de una función booleana al conjunto de las funciones afines. La familia de funciones bent son las funciones booleanas de un número par de variables con la máxima no linealidad, aunque no son equilibradas. A pesar de su definición simple y natural, las funciones bent poseen una estructura complicada en general. La construcción de funciones criptográficamente completas es una tarea ardua. Actualmente existe una amplia gama de técnicas algebraicas y heurísticas para construir tales funciones, sin embargo estos métodos pueden ser complejos, computacionalmente difíciles para su implementación y no siempre producen una variedad suficiente de funciones. Nuestro esfuerzo principal se ha centrado en el diseño de métodos de construcción para obtener el mayor número posible de nuevas funciones bent. Hay diferentes métodos para obtener funciones bent, muchos de ellos basados en la forma normal algebraica de una función booleana y en la transformada de Fourier (o Walsh). Sin embargo, nosotros utilizamos la representación clásica de las funciones booleanas a través de minterms para construir funciones bent de cualquier número par de variables a partir de otras funciones booleanas de menor número de variables. Hemos adoptado esta técnica dada la imposibilidad de obtener, de forma aleatoria, funciones bent de más de 6 variables. La memoria de investigación se divide en cuatro capítulos. En el primer capítulo proporcionamos una extensa introducción sobre la importancia de las funciones booleanas en la criptografía y repasamos brevemente la historia de las funciones bent a lo largo de estas últimas cuatro décadas. Además presentamos, de manera breve, los conceptos principales relativos a las funciones booleanas y la notación que necesitaremos para la comprensión de los resultados mostrados en esta memoria. Por último, introducimos algunas de las construcciones clásicas de funciones bent más conocidas, lo que nos permitirá poder realizar una comparación exhaustiva con los métodos de construcción que presentamos en los capítulos siguientes. En el segundo capítulo presentamos dos métodos de construcción de funciones bent de n+2 variables basados en la utilización de funciones bent de n de variables (con n par). Calculamos el número de funciones bent distintas que podemos obtener con cada una de dichas construcciones, proporcionando así una cota inferior del número de funciones bent de cualquier número de variables. Al final del capítulo, comparamos nuestras construcciones con algunos de los métodos de construcción de funciones bent más conocidos. En el tercer capítulo definimos dos nuevas funciones bent de n variables, denominadas funciones de máximo y mínimo peso, construidas a partir de una función bent de n variables y algunas funciones lineales. Analizamos las propiedades principales de estas nuevas funciones y proporcionamos un nuevo método de construcción de funciones bent de n+2 variables basado en el uso de las funciones de máximo y mínimo peso de n variables y de los minterms de 2 variables. Introducimos algunos resultados necesarios para contar el número de funciones bent proporcionado por la nueva construcción; y, por último, comparamos dicho método con las construcciones clásicas introducidas al final del primer capítulo mostrando las diferencias entre éstos. Y para finalizar, en el último capítulo introducimos el último método de construcción de funciones bent que presentamos en esta memoria. Esta construcción se basa en la utilización de funciones booleanas de n variables (ahora con n impar) y en el uso de los cuatro minterms de 2 variables para la obtención de funciones bent de n+1 variables. La diferencia con respecto a las construcciones presentadas anteriormente, es que la generación de estas nuevas funciones bent se basa en el empleo de funciones booleanas de n variables. Para la construcción explícita de estas funciones booleanas utilizamos funciones bent de n-1 variables. Analizamos algunas propiedades interesantes de las funciones booleanas implicadas en esta nueva construcción, lo que nos permitirá poder obtener la forma explícita de éstas y, por tanto, de la construcción. Finalmente, establecemos el número de funciones bent que podemos obtener a través del método introducido en este capítulo y lo comparamos con otros métodos de construcción de funciones bent conocidos. La memoria termina con la relación de la bibliografía utilizada para su elaboración.