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.

On the realization of Boolean functions using AND and OR elements /

Thesis (M. S.)--University of Illinois at Urbana-Champaign.

The pattern articulation unit of Illiac III; homogenous Boolean functions in the iterative array,

"Supported in part by Contract AT(11-1) 1018 with the U.S. Atomic Energy Commission and the Advanced Research Projects Agency."

Essential Arity Gap of Boolean Functions

In this paper we investigate the Boolean functions with maximum essential arity gap. Additionally we propose a simpler proof of an important theorem proved by M. Couceiro and E. Lehtonen in [3]. They use Zhegalkin’s polynomials as normal forms for Boolean functions and describe the functions with essential arity gap equals 2. We use to instead Full Conjunctive Normal Forms of these polynomials which allows us to simplify the proofs and to obtain several combinatorial results concerning the Boolean functions with a given arity gap. The Full Conjunctive Normal Forms are also sum of conjunctions, in which all variables occur.

Decomposition of Boolean Functions – Recognizing a Good Solution by Traces

The problem of sequent two-block decomposition of a Boolean function is regarded in case when a good solution does exist. The problem consists mainly in finding an appropriate weak partition on the set of arguments of the considered Boolean function, which should be decomposable at that partition. A new fast heuristic combinatorial algorithm is offered for solving this task. At first the randomized search for traces of such a partition is fulfilled. The recognized traces are represented by some "triads" - the simplest weak partitions corresponding to non-trivial decompositions. After that the whole sought-for partition is restored from the discovered trace by building a track initialized by the trace and leading to the solution. The results of computer experiments testify the high practical efficiency of the algorithm.

Implementation of a Heuristic Method of Decomposition of Partial Boolean Functions

An original heuristic algorithm of sequential two-block decomposition of partial Boolean functions is researched. The key combinatorial task is considered: finding of suitable partition on the set of arguments, i. e. such one, on which the function is separable. The search for suitable partition is essentially accelerated by preliminary detection of its traces. Within the framework of the experimental system the efficiency of the algorithm is evaluated, the boundaries of its practical application are determined.

On some Properties of Boolean Functions and Their Binary Decision Diagrams

Иво Й. Дамянов - Манипулирането на булеви функции е основнo за теоретичната информатика, в това число логическата оптимизация, валидирането и синтеза на схеми. В тази статия се разглеждат някои първоначални резултати относно връзката между граф-базираното представяне на булевите функции и свойствата на техните променливи.

Dynamics of a class of ODEs more general than almost periodic

A temporally global solution, if it exists, of a nonautonomous ordinary differential equation need not be periodic, almost periodic or almost automorphic when the forcing term is periodic, almost periodic or almost automorphic, respectively. An alternative class of functions extending periodic and almost periodic functions which has the property that a bounded temporally global solution solution of a nonautonomous ordinary differential equation belongs to this class when the forcing term does is introduced here. Specifically, the class of functions consists of uniformly continuous functions, defined on the real line and taking values in a Banach space, which have pre-compact ranges. Besides periodic and almost periodic functions, this class also includes many nonrecurrent functions. Assuming a hyperbolic structure for the unperturbed linear equation and certain properties for the linear and nonlinear parts, the existence of a special bounded entire solution, as well the existence of stable and unstable manifolds of this solution are established. Moreover, it is shown that this solution and these manifolds inherit the temporal behaviour of the vector field equation. In the stable case it is shown that this special solution is the pullback attractor of the system. A class of infinite dimensional examples involving a linear operator consisting of a time independent part which generates a C(0)-semigroup plus a small time dependent part is presented and applied to systems of coupled heat and beam equations. (C) 2010 Elsevier Ltd. All rights reserved.

Medidas não convencionais de transferências de função entre expressões faciais e figuras abstratas

Relações de equivalência podem ser definidas como relações arbitrárias capazes de tornar diferentes estímulos intercambiáveis em muitas situações. Isso implica que os elementos que compõem uma classe de estímulos equivalentes devem transferir funções entre si. Este trabalho compreende dois estudos que possuem em comum a formação de classes de equivalência entre expressões faciais e figuras abstratas e o uso de medidas não convencionais de transferência de função. No Experimento 1, foram treinadas relações condicionais entre expressões faciais (A) e estímulos abstratos (conjuntos B e C) e entre os estímulos do conjunto C com os de outro conjunto (D). A equivalência foi testada pelas relações D-B. ‘A’ era composto por fotografias que expressavam alegria, raiva e nojo, enquanto B, C e D se compunham por três figuras abstratas cada. Era então pedido ao participante que avaliasse os estímulos abstratos D1, D2 e D3 de acordo com um conjunto de escalas bipolares. Foi encontrada correspondência entre as avaliações das expressões faciais feitas pelo grupo controle e as avaliações dos estímulos D pelo grupo experimental. O uso de estímulos significativos e de medidas de transferência que não envolviam escolhas forçadas possibilitaram uma validação independente do modelo de equivalência, mostrando que estímulos arbitrários podem adquirir 'significado' similar ao de expressões faciais. Os resultados permitem ainda avaliar o grau em que os símbolos adquiriram o significado dos referentes. O Experimento 2 considerou o fato de que uma expressão facial ameaçadora em meio a expressões amigáveis é selecionada mais rapidamente que uma expressão amigável em meio a ameaçadoras e verificou se o mesmo ocorreria com os estímulos que se tornassem equivalentes a elas. As mesmas relações do Experimento 1 foram treinadas e testadas. Um pós-teste dispunha três figuras relacionadas à mesma expressão facial e uma que pertencia à classe de outro rosto. O participante devia selecionar rapidamente essa última. Os símbolos relacionados à expressão ameaçadora foram selecionados mais rapidamente que os relacionados à face amigável, indicando que esse efeito pode se transferir através de relações de equivalência.

Constraint-based analysis of gene interactions using restricted boolean networks and time-series data

Abstract Background A popular model for gene regulatory networks is the Boolean network model. In this paper, we propose an algorithm to perform an analysis of gene regulatory interactions using the Boolean network model and time-series data. Actually, the Boolean network is restricted in the sense that only a subset of all possible Boolean functions are considered. We explore some mathematical properties of the restricted Boolean networks in order to avoid the full search approach. The problem is modeled as a Constraint Satisfaction Problem (CSP) and CSP techniques are used to solve it. Results We applied the proposed algorithm in two data sets. First, we used an artificial dataset obtained from a model for the budding yeast cell cycle. The second data set is derived from experiments performed using HeLa cells. The results show that some interactions can be fully or, at least, partially determined under the Boolean model considered. Conclusions The algorithm proposed can be used as a first step for detection of gene/protein interactions. It is able to infer gene relationships from time-series data of gene expression, and this inference process can be aided by a priori knowledge available.

Noisy random Boolean formulae:a statistical physics perspective

Properties of computing Boolean circuits composed of noisy logical gates are studied using the statistical physics methodology. A formula-growth model that gives rise to random Boolean functions is mapped onto a spin system, which facilitates the study of their typical behavior in the presence of noise. Bounds on their performance, derived in the information theory literature for specific gates, are straightforwardly retrieved, generalized and identified as the corresponding macroscopic phase transitions. The framework is employed for deriving results on error-rates at various function-depths and function sensitivity, and their dependence on the gate-type and noise model used. These are difficult to obtain via the traditional methods used in this field.