Departamento de Computación

En el ámbito de la criptografía, las funciones booleanas juegan un papel importante ya que estas son el elemento principal en el desarrollo de algunos cripto-sistemas como: los cifradores por bloques, funciones hash y principalmente cajas de sustitución. Para que estas puedan ser utilizadas, deben satisfacer uno o más criterios, como el del balance para evitar que los cripto-sistemas proporcionen información del texto en claro cuando el atacante posee el texto cifrado y el criterio de no linealidad, con el que los sistemas criptográficos se hacen resistentes al criptoanálisis lineal desarrollado por Matsuy. El optimizar la propiedad de no a linealidad de las funciones booleanas manteniendo el criterio de balance es un problema difícil de tratar ya que el número de funciones booleanas crece de manera doblemente exponencial.
En este trabajo presentamos el desarrollo de un método para localizar funciones booleanas balanceadas con máxima no linealidad utilizando los algoritmos de búsqueda local y recocido simulando, y un método para seleccionar puntos sobre el espacio de búsqueda, el cual utiliza una estructura de gráfica para representar el espacio de las funciones booleanas balanceadas, una representación de las funciones booleanas basadas en patrones y la teoría de cúmulos. Nuestro propósito ha sido localizar patrones que guíen búsquedas para la maximización de la no-linealidad sujetos a la restricción de balance y hemos optado por considerar algoritmos deterministas. El uso de algoritmos de tipo heurístico o evolutivo queda fuera de los alcances de esta tesis.
Dentro del desarrollo de la metodología se presenta una biblioteca de funciones para medir y optimizar la no linealidad de las funciones booleanas, para que nuevas heurísticas sean desarrolladas a partir de los resultados obtenidos.