Soporte, grado y no linealidad perfecta de funciones booleanas

Resum

INTRODUCCIÓN Las funciones booleanas son una poderosa herramienta para modelar una gran cantidad de procesos de interés en la lógica, la ingeniería, la ciencia o las matemáticas. Por citar un ejemplo, el código genético natural está compuesto de manera única por solo dos pares de bases codificables como secuencias binarias. Particularmente, criptografía se hace un uso intensivo de las mismas en la construcción y análisis de criptosistemas. Las funciones booleanas juegan un papel importante en los cifradores en bloque, los cifradores en flujo,las funciones hash y la teoría de Códigos, entre otras. En los modelos más comunes de cifradores en flujo, la clave se produce utilizando una función booleana. La selección de las funciones booleanas atendiendo a una amplia variedad de criterios permite aumentar notablemente la seguridad de las claves producidas. La implementación de una caja de sustitución o S-box necesita funciones booleanas no lineales que posean ciertas propiedades criptográficas favorables para garantizar la resistencia a ataques tales como el criptoanálisis lineal y el diferencial. DESARROLLO Y CONCLUSIONES Después de recopilar brevemente la historia de las funciones bent a lo largo de estas últimas cuatro décadas y enunciar los resultados preliminares necesarios para la comprensión y entendimiento de la notación utilizada, se demuestran una serie de propiedades del grado de las funciones booleanas y se construyen algoritmos basados en ellas, útiles para determinar computacionalmente el grado partiendo del soporte o tabla de verdad que define a la función. También se presentan construcciones de funciones de no linealidad perfecta teniendo como punto de partida bases de un espacio vectorial sobre el cuerpo de Galois. Por último, se introducen construcciones de una clase especial de funciones de no linealidad perfecta, conocidas como Partial Spread, planteando una serie de cuestiones abiertas que merecería la pena investigar en el futuro.