1,721,021 research outputs found
Building Correlation Immune Functions from Sets of Mutually Orthogonal Cellular Automata
Full text linkCorrelation immune Boolean functions play an important role in the implementation of efficient masking countermeasures for side-channel attacks in cryptography. In this paper, we investigate a method to construct correlation immune functions through families of mutually orthogonal cellular automata (MOCA). First, we show that the orthogonal array (OA) associated to a family of MOCA can be expanded to a binary OA of strength at least 2. To prove this result, we exploit the characterization of MOCA in terms of orthogonal labelings on de Bruijn graphs. Then, we use the resulting binary OA to define the support of a second-order correlation immune function. Next, we perform some computational experiments to construct all such functions up to n= 12 variables, and observe that their correlation immunity order is actually greater, always at least 3. We conclude by discussing how these results open up interesting perspectives for future research, with respect to the search of new correlation-immune functions and binary orthogonal arrays.</p
On the Minimum Distance of Subspace Codes Generated by Linear Cellular Automata
Full text linkMotivated by applications to noncoherent network coding, we study subspace codes defined by sets of linear cellular automata (CA). As a first remark, we show that a family of linear CA where the local rules have the same diameter—and thus the associated polynomials have the same degree—induces a Grassmannian code. Then, we prove that the minimum distance of such a code is determined by the maximum degree occurring among the pairwise greatest common divisors (GCD) of the polynomials in the family. Finally, we consider the setting where all such polynomials have the same GCD, and determine the cardinality of the corresponding Grassmannian code. As a particular case, we show that if all polynomials in the family are pairwise coprime, the resulting Grassmannian code has the highest minimum distance possible.</p
Balanced crossover operators in Genetic Algorithms
Full text linkIn several combinatorial optimization problems arising in cryptography and design theory, the admissible solutions must often satisfy a balancedness constraint, such as being represented by bitstrings with a fixed number of ones. For this reason, several works in the literature tackling these optimization problems with Genetic Algorithms (GA) introduced new balanced crossover operators which ensure that the offspring has the same balancedness characteristics of the parents. However, the use of such operators has never been thoroughly motivated, except for some generic considerations about search space reduction. In this paper, we undertake a rigorous statistical investigation on the effect of balanced and unbalanced crossover operators against three optimization problems from the area of cryptography and coding theory: nonlinear balanced Boolean functions, binary Orthogonal Arrays (OA) and bent functions. In particular, we consider three different balanced crossover operators (each with two variants: “left-to-right” and “shuffled”), two of which have never been published before, and compare their performances with classic one-point crossover. We are able to confirm that the balanced crossover operators perform better than one-point crossover. Furthermore, in two out of three crossovers, the “left-to-right” version performs better than the “shuffled” version
The Influence of Local Search on Genetic Algorithms with Balanced Representations
No full textCertain combinatorial optimization problems with binary representation require the candidate solutions to satisfy a balancedness constraint (e.g., being composed of the same number of 0s and 1s). A common strategy when using Genetic Algorithms (GA) to solve these problems is to use crossoveer and mutation operators that preserve balancedness in the offspring. However, it has been observed that the reduction of the search space size granted by such tailored variation operators does not usually translate to a substantial improvement of the GA performance. There is still no clear explanation of this phenomenon, although it is suspected that a balanced representation might yield a more irregular fitness landscape, where it could be more difficult for GA to converge to a global optimum. In this paper, we investigate this issue by adding a local search step to a GA with balanced operators, and use it to evolve highly nonlinear balanced Boolean functions. We organize our experiments around two research questions, namely if local search (1) improves the convergence speed of GA, and (2) decreases the population diversity. Surprisingly, while our results answer affirmatively the first question, they also show that adding local search actually increases the diversity among the individuals. We link these findings to some recent results on fitness landscape analysis for problems on Boolean functions
A classification of S-boxes generated by orthogonal cellular automata
Full text linkMost of the approaches published in the literature to construct S-boxes via Cellular Automata (CA) work by either iterating a finite CA for several time steps, or by a one-shot application of the global rule. The main characteristic that brings together these works is that they employ a single CA rule to define the vectorial Boolean function of the S-box. In this work, we explore a different direction for the design of S-boxes that leverages on Orthogonal CA (OCA), i.e. pairs of CA rules giving rise to orthogonal Latin squares. The motivation stands on the facts that an OCA pair already defines a bijective transformation, and moreover the orthogonality property of the resulting Latin squares ensures a minimum amount of diffusion. We exhaustively enumerate all S-boxes generated by OCA pairs of diameter 4≤d≤6, and measure their nonlinearity. Interestingly, we observe that for d=4 and d=5 all S-boxes are linear, despite the underlying CA local rules being nonlinear. The smallest nonlinear S-boxes emerges for d=6, but their nonlinearity is still too low to be used in practice. Nonetheless, we unearth an interesting structure of linear OCA S-boxes, proving that their Linear Components Space is itself the image of a linear CA, or equivalently a polynomial code. We finally classify all linear OCA S-boxes in terms of their generator polynomials.</p
Search space reduction of asynchrony immune cellular automata
Full text linkWe continue the study of asynchrony immunity in cellular automata (CA), which can be considered as a generalization of correlation immunity in the case of vectorial Boolean functions. The property could have applications as a countermeasure for side-channel attacks in CA-based cryptographic primitives, such as S-boxes and pseudorandom number generators. We first give some theoretical results on the properties that a CA rule must satisfy in order to meet asynchrony immunity, like central permutivity. Next, we perform an exhaustive search of all asynchrony immune CA rules of neighborhood size up to 5, leveraging on the discovered theoretical properties to greatly reduce the size of the search space.Cyber Securit
Evolving Cryptographic Boolean Functions with Reaction Systems
No full textDesigning bent Boolean functions for cryptographic applications is a challenging combinatorial task due to the super-exponential growth of the search space. We propose Evolutionary Boolean Reaction Systems (EvoBRS), an optimization method based on Reaction Systems (RS)—a bio-inspired model abstracting biochemical reactions. EvoBRS finds functions with competitive nonlinearity while providing a compact and interpretable representation. Unlike traditional methods such as Genetic Algorithms (GA), which rely on full truth tables, EvoBRS leverages a more expressive yet concise encoding
Cellular Automata Pseudo-Random Number Generators and Their Resistance to Asynchrony
No full textCellular Automata (CA) have a long history being employed as pseudo-random number generators (PRNG), especially for cryptographic applications such as keystream generation in stream ciphers. Initially starting from the study of rule 30 of elementary CA, multiple rules where the objects of investigation and were shown to be able to pass most of the rigorous statistical tests used to assess the quality of PRNG. In all cases, the CA employed where of the classical, synchronous kind. This assumes a global clock regulating all CA updates which can be a weakness if an attacker is able to tamper it. Here we study how much asynchrony is necessary to make a CA-based PRNG ineffective. We have found that elementary CA are subdivided into three class: (1) there is a “state transition” where, after a certain level of asynchrony, the CA loses the ability to generate strong random sequences, (2) the randomness of the sequences increases with a limited level of asynchrony, or (3) CA normally unable to be used as PRNG exhibit a much stronger ability to generate random sequences when asynchrony is introduced
Does constraining the search space of GA always help?
No full textIn this paper, we undertake an investigation on the effect of balanced and unbalanced crossover operators against the problem of finding non-linear balanced Boolean functions: we consider three different balanced crossover operators and compare their performances with classic one-point crossover. The statistical comparison shows that the use of balanced crossover operators gives GA a definite advantage over one-point crossover
- …
