@unpublished{upm64788,
         address = {Madrid},
           month = {July},
           title = {Algoritmos heur{\'i}sticos para la optimizaci{\'o}n de Substitution Boxes},
            year = {2020},
          author = {Emiliano Santos Jim{\'e}nez},
        keywords = {Criptolog{\'i}a; Ciberseguridad},
             url = {https://oa.upm.es/64788/},
        abstract = {En pleno siglo XXI, la ciberseguridad es ya una parte importante de la vida cotidiana de muchos ciudadanos. La protecci{\'o}n de la informaci{\'o}n y la defensa contra ataques
cibern{\'e}ticos es ya algo fundamental y, dentro de este {\'a}mbito, el cifrado se ha vuelto una pieza imprescindible en tales tareas. Por ello, el desarrollo de nuevos m{\'e}todos de cifrado cada vez es m{\'a}s relevante. Por otro lado, la Inteligencia Artificial ha sufrido un auge notorio durante la {\'u}ltima d{\'e}cada. Sus t{\'e}cnicas ya son cada vez m{\'a}s empleadas en diferentes contextos, entre los que se encuentra la ciberseguridad. Este proyecto aborda la aplicaci{\'o}n de t{\'e}cnicas de Inteligencia Artificial para la mejora de diferentes aspectos, relacionados con la  criptolog{\'i}a, en el {\'a}mbito de la ciberseguridad. Una S-Box es un componente importante del cifrado en bloque, cuyo objetivo es transformar una entrada de n bits en una salida diferente de m bits. En la {\'u}ltima d{\'e}cada varios
investigadores han intentado descubrir nuevas formas de crear S-Boxes. La aplicaci{\'o}n de t{\'e}cnicas heur{\'i}sticas (t{\'e}cnicas pertenecientes al campo de la Inteligencia Artificial) para generar S-Boxes con buenas propiedades criptogr{\'a}ficas ha cogido mucha relevancia en relaci{\'o}n a m{\'e}todos m{\'a}s convencionales. El enfoque que se aplica en este proyecto consiste en adaptar el m{\'e}todo cient{\'i}fico para crear un algoritmo heur{\'i}stico que optimice algunas
de las propiedades criptogr{\'a}ficas (m{\'a}s concretamente la no-linealidad) de estos componentes el cifrado en bloque. M{\'a}s concretamente, la propuesta de este proyecto consiste
en desarrollar un m{\'e}todo constructivo que genera de forma aleatoria una serie de soluciones iniciales sobre las que posteriormente se aplicar{\'a} una b{\'u}squeda local cuyo objetivo es mejorar las soluciones iniciales. Por {\'u}ltimo se aplica una versi{\'o}n de la metaheur{\'i}stica Variable
Neighborhood Search con la finalidad de evitar los {\'o}ptimos locales que se producen con la b{\'u}squeda y tratar de alcanzar un mejor resultado. Los algoritmos propuestos han
sido validados mediante la realizaci{\'o}n de pruebas que comparan los tres m{\'e}todos desarrollados. El tiempo de ejecuci{\'o}n de las pruebas aumenta exponencialmente cuanto mayor es la dimensi{\'o}n de la instancia tratada, siendo el tama{\~n}o m{\'a}ximo que se ha considerado en este proyecto de 8x8. Los resultados obtenidos con el constructivo aleatorio muestran valores iniciales prometedores. Sin embargo, esto parece indicar que los valores pueden
estar pr{\'o}ximos a los {\'o}ptimos locales, siendo dif{\'i}cil la propuesta de algoritmos de mejora. 
Abtract:
Nowadays, cibersecurity is an important part of the daily life of many citizens. Protecting data and defending against attacks have already become fundamental, and within this area, encrypting has become an essential part in such tasks. This is the reason why developing new encryption methods is increasingly important. On the other hand, Artificial Ingelligence has experienced a boom during the last decade. Its techniques are gradually more used in different contexts, among which is cybersecurity.
This project approach the aplication of Artificial Intelligence to improve different aspects related to cryptology, in the context of cibersecurity. An S-Box is an important component of block ciphers, which aim is transform a n bits input into a m bits output. For the last decade, some researchers have tried to find new methods to create S-Boxes. The application of heuristic techniques, which are part of Artificial Intelligence context, to produce S-Boxes with strong cryptological properties has obtained more relevance compared to conventional methods. The approach proposed in this project is to use the scientific method in order to generate an heuristic algorithm to optimize some of those S-Boxes cryptological properties (specifically non linearity). To be more accurate, this project proposes developing a constructive method which create a number of solutions randomly and use a local search in order to improve the initial solutions. Finally, the Variable Neighborhood Search metaheuristic is applied trying to avoid local optima produced by the local search and improve the overall results. The methods proposed have been validated with tests comparing the three methods. The ejecution time of the tests increases exponentially the larger the size of the instance, being 8x8 the maximum size considered in this project. The results obtained with the random consctructive method shows promising initial values.  However, this seems to indicate that those values could be near local optima, making the proposal of improvement algorithms harder.}
}