Vector Boolean Functions: Applications in Symmetric Cryptography

Esta tesis establece los fundamentos teóricos y diseña una colección 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 criptográfica. Esta nueva implementación emplea la librería NTL de Victor Shoup, incorporando nuevos módulos que complementan a las funciones de NTL, adecuándolas para el análisis criptográfico. La clase fundamental que representa una función booleana vectorial se puede inicializar de manera muy flexible mediante diferentes estructuras de datas tales como la Tabla de verdad, la Representación de traza y la Forma algebraica normal entre otras. De esta manera VBF permite evaluar los criterios criptográficos más relevantes de los algoritmos de cifra en bloque y de stream, así como funciones hash: por ejemplo, proporciona la no-linealidad, la distancia lineal, el grado algebraico, las estructuras lineales, la distribución de frecuencias de los valores absolutos del espectro Walsh o del espectro de autocorrelación, entre otros criterios. Adicionalmente, VBF puede llevar a cabo operaciones entre funciones booleanas vectoriales tales como la comprobación de igualdad, la composición, la inversión, la suma, la suma directa, el bricklayering (aplicación paralela de funciones booleanas vectoriales como la empleada en el algoritmo de cifra Rijndael), y la adición de funciones coordenada. La tesis también muestra el empleo de la librería VBF en dos aplicaciones prácticas. Por un lado, se han analizado las características más relevantes de los sistemas de cifra en bloque. Por otro lado, combinando VBF con algoritmos de optimización, se han diseñado funciones booleanas cuyas propiedades criptográficas 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.

Learning an L1-regularized Gaussian Bayesian Network in the Equivalence Class Space

Learning the structure of a graphical model from data is a common task in a wide range of practical applications. In this paper, we focus on Gaussian Bayesian networks, i.e., on continuous data and directed acyclic graphs with a joint probability density of all variables given by a Gaussian. We propose to work in an equivalence class search space, specifically using the k-greedy equivalence search algorithm. This, combined with regularization techniques to guide the structure search, can learn sparse networks close to the one that generated the data. We provide results on some synthetic networks and on modeling the gene network of the two biological pathways regulating the biosynthesis of isoprenoids for the Arabidopsis thaliana plant

Cryptographic properties of Boolean functions defining elementary cellular automata

In this work, the algebraic properties of the local transition functions of elementary cellular automata (ECA) were analysed. Specifically, a classification of such cellular automata was done according to their algebraic degree, the balancedness, the resiliency, nonlinearity, the propagation criterion and the existence of non-zero linear structures. It is shown that there is not any ECA satisfying all properties at the same time.

Bit noise from an optical logic gate with laser diodes

Output bits from an optical logic cell present noise due to the type of technique used to obtain the Boolean functions of two input data bits. We have simulated the behavior of an optically programmable logic cell working with Fabry Perot-laser diodes of the same type employed in optical communications (1550nm) but working here as amplifiers. We will report in this paper a study of the bit noise generated from the optical non-linearity process allowing the Boolean function operation of two optical input data signals. Two types of optical logic cells will be analyzed. Firstly, a classical "on-off" behavior, with transmission operation of LD amplifier and, secondly, a more complicated configuration with two LD amplifiers, one working on transmission and the other one in reflection mode. This last configuration has nonlinear behavior emulating SEED-like properties. In both cases, depending on the value of a "1" input data signals to be processed, a different logic function can be obtained. Also a CW signal, known as control signal, may be apply to fix the type of logic function. The signal to noise ratio will be analyzed for different parameters, as wavelength signals and the hysteresis cycles regions associated to the device, in relation with the signals power level applied. With this study we will try to obtain a better understanding of the possible effects present on an optical logic gate with Laser Diodes.

Optical regeneration based on noise generated in bistable devices: going from 2R to 3R

In this paper we propose to employ an instability that occurs in bistable devices as a control signal at the reception stage to generate the clock signal. One of the adopted configurations is composed of two semiconductor optical amplifiers arranged in a cascaded structure. This configuration has an output equivalent to that obtained from Self-Electrooptic Effect Devices (SEEDs), and it can implement the main Boolean functions of two binary inputs. These outputs, obtained from the addition of two binary signals, show a short spike in the transition from "1" to "2" in the internal processing. A similar result is obtained for a simple semiconductor amplifier with bistable behavior. The paper will show how these structures may help recover clock signals in any optical transmission system

Image characterisation based on the mammalian visual cortex

A proposal for a model of the primary visual cortex is reported. It is structured with the basis of a simple unit cell able to perform fourteen pairs of different boolean functions corresponding to the two possible inputs. As a first step, a model of the retina is presented. Different types of responses, according to the different possibilities of interconnecting the building blocks, have been obtained. These responses constitute the basis for an initial configuration of the mammalian primary visual cortex. Some qualitative functions, as symmetry or size of an optical input, have been obtained. A proposal to extend this model to some higher functions, concludes the paper.

Determining the effectiveness of three software evaluation techniques through informal aggregation

An accepted fact in software engineering is that software must undergo verification and validation process during development to ascertain and improve its quality level. But there are too many techniques than a single developer could master, yet, it is impossible to be certain that software is free of defects. So, it is crucial for developers to be able to choose from available evaluation techniques, the one most suitable and likely to yield optimum quality results for different products. Though, some knowledge is available on the strengths and weaknesses of the available software quality assurance techniques but not much is known yet on the relationship between different techniques and contextual behavior of the techniques. Objective: This research investigates the effectiveness of two testing techniques ? equivalence class partitioning and decision coverage and one review technique ? code review by abstraction, in terms of their fault detection capability. This will be used to strengthen the practical knowledge available on these techniques.

Einstein-like geometric structures on surfaces

An AH (affine hypersurface) structure is a pair comprising a projective equivalence class of torsion-free connections and a conformal structure satisfying a compatibility condition which is automatic in two dimensions. They generalize Weyl structures, and a pair of AH structures is induced on a co-oriented non-degenerate immersed hypersurface in flat affine space. The author has defined for AH structures Einstein equations, which specialize on the one hand to the usual Einstein Weyl equations and, on the other hand, to the equations for affine hyperspheres. Here these equations are solved for Riemannian signature AH structures on compact orientable surfaces, the deformation spaces of solutions are described, and some aspects of the geometry of these structures are related. Every such structure is either Einstein Weyl (in the sense defined for surfaces by Calderbank) or is determined by a pair comprising a conformal structure and a cubic holomorphic differential, and so by a convex flat real projective structure. In the latter case it can be identified with a solution of the Abelian vortex equations on an appropriate power of the canonical bundle. On the cone over a surface of genus at least two carrying an Einstein AH structure there are Monge-Amp`ere metrics of Lorentzian and Riemannian signature and a Riemannian Einstein K"ahler affine metric. A mean curvature zero spacelike immersed Lagrangian submanifold of a para-K"ahler four-manifold with constant para-holomorphic sectional curvature inherits an Einstein AH structure, and this is used to deduce some restrictions on such immersions.

A finite class of orthogonal functions generated by Routh-Romanovski polynomials

It is known that some orthogonal systems are mapped onto other orthogonal systems by the Fourier transform. In this article we introduce a finite class of orthogonal functions, which is the Fourier transform of Routh-Romanovski orthogonal polynomials, and obtain its orthogonality relation using Parseval identity.