Vector Boolean Functions: Applications in Symmetric Cryptography
Alvarez Cubero, José Antonio · 2015
Esta tesis establece los fundamentos teoricos y disena una coleccion abierta de clases C++ denominada VBF (Vector Boolean Functions) para analizar funciones booleanas vectoriales (funciones que asocian un vector booleano a otro vector booleano) desde una perspectiva criptografica. Esta nueva implementacion emplea la libreria NTL de Victor Shoup, incorporando nuevos modulos que complementan a las funciones de NTL, adecuandolas para el analisis criptografico. La clase fundamental que representa una funcion booleana vectorial se puede inicializar de manera muy flexible mediante diferentes estructuras de datas tales como la Tabla de verdad, la Representacion de traza y la Forma algebraica normal entre otras. De esta manera VBF permite evaluar los criterios criptograficos mas relevantes de los algoritmos de cifra en bloque y de stream, asi como funciones hash: por ejemplo, proporciona la no-linealidad, la distancia lineal, el grado algebraico, las estructuras lineales, la distribucion de frecuencias de los valores absolutos del espectro Walsh o del espectro de autocorrelacion, entre otros criterios. Adicionalmente, VBF puede llevar a cabo operaciones entre funciones booleanas vectoriales tales como la comprobacion de igualdad, la composicion, la inversion, la suma, la suma directa, el bricklayering (aplicacion paralela de funciones booleanas vectoriales como la empleada en el algoritmo de cifra Rijndael), y la adicion de funciones coordenada. La tesis tambien muestra el empleo de la libreria VBF en dos aplicaciones practicas. Por un lado, se han analizado las caracteristicas mas relevantes de los sistemas de cifra en bloque. Por otro lado, combinando VBF con algoritmos de optimizacion, se han disenado funciones booleanas cuyas propiedades criptograficas son las mejores conocidas hasta la fecha. ABSTRACT This thesis develops the theoretical foundations and designs an open collection of C++ classes, called VBF, designed for analyzing vector Boolean functions (functions that map a Boolean vector to another Boolean vector) from a cryptographic perspective. This new implementation uses the NTL library from Victor Shoup, adding new modules which complement the existing ones making VBF better suited for cryptography. The fundamental class representing a vector Boolean function can be initialized in a flexible way via several alternative types of data structures such as Truth Table, Trace Representation, Algebraic Normal Form (ANF) among others. This way, VBF allows the evaluation of the most relevant cryptographic criteria for block and stream ciphers as well as for hash functions: for instance, it provides the nonlinearity, the linearity distance, the algebraic degree, the linear structures, the frequency distribution of the absolute values of the Walsh Spectrum or the Autocorrelation Spectrum, among others. In addition, VBF can perform operations such as equality testing, composition, inversion, sum, direct sum, bricklayering (parallel application of vector Boolean functions as employed in Rijndael cipher), and adding coordinate functions of two vector Boolean functions. This thesis also illustrates the use of VBF in two practical applications. On the one hand, the most relevant properties of the existing block ciphers have been analysed. On the other hand, by combining VBF with optimization algorithms, new Boolean functions have been designed which have the best known cryptographic properties up-to-date.