We consider the problem of evolving a particular kind of shift-invariant transformation – namely, Reversible Cellular Automata (RCA) defined by conserved landscape rules – using GA and GP. To this end, we employ three different optimization strategies: a single-objective approach carried out with GA and GP where only the reversibility constraint of marker CA is considered, a multi-objective approach based on GP where both reversibility and the Hamming weight are taken into account, and a lexicographic approach where GP first optimizes only the reversibility property until a conserved landscape rule is obtained, and then maximizes the Hamming weight while retaining reversibility. The results are discussed in the context of three different research questions stemming from exhaustive search experiments on conserved landscape CA, which concern (1) the difficulty of the associated optimization problem for GA and GP, (2) the utility of conserved landscape CA in the domain of cryptography and reversible computing, and (3) the relationship between the reversibility property and the Hamming weight.

Finding optimal adversarial dynamics between defenders and attackers in large network systems is a complex problem one can approach from several perspectives. The results obtained are often not satisfactory since they either concentrate on only one party or run very simplified scenarios that are hard to correlate with realistic settings. To truly find which are the most robust defensive strategies, the adaptive attacker ecosystem must be given as many degrees of freedom as possible, to model real attacking scenarios accurately. We propose a coevolutionary-based simulator called MOVE that can evolve both attack and defense strategies. To test it, we investigate several different but realistic scenarios, taking into account features such as network topology and possible applications in the network. The results show that the evolved strategies far surpass randomly generated strategies. Finally, the evolved strategies can help us to reach some more general conclusions for both attacker and defender sides.

Genetic programming is an often-used technique for symbolic regression: finding symbolic expressions that match data from an unknown function. To make the symbolic regression more efficient, one can also use dimensionally-aware genetic programming that constrains the physical units of the equation. Nevertheless, there is no formal analysis of how much dimensionality awareness helps in the regression process. In this paper, we conduct a fitness landscape analysis of dimensionally-aware genetic programming search spaces on a subset of equations from Richard Feynman’s well-known lectures. We define an initialisation procedure and an accompanying set of neighbourhood operators for conducting the local search within the physical unit constraints. Our experiments show that the added information about the variable dimensionality can efficiently guide the search algorithm. Still, further analysis of the differences between the dimensionally-aware and standard genetic programming landscapes is needed to help in the design of efficient evolutionary operators to be used in a dimensionally-aware regression.

Tasks related to Natural Language Processing (NLP) have recently been the focus of a large research endeavor by the machine learning community. The increased interest in this area is mainly due to the success of deep learning methods. Genetic Programming (GP), however, was not under the spotlight with respect to NLP tasks. Here, we propose a first proof-of-concept that combines GP with the well established NLP tool word2vec for the next word prediction task. The main idea is that, once words have been moved into a vector space, traditional GP operators can successfully work on vectors, thus producing meaningful words as the output. To assess the suitability of this approach, we perform an experimental evaluation on a set of existing newspaper headlines. Individuals resulting from this (pre-)training phase can be employed as the initial population in other NLP tasks, like sentence generation, which will be the focus of future investigations, possibly employing adversarial co-evolutionary approaches.

Substitution boxes (S-boxes) are nonlinear mappings that represent one of the core parts of many cryptographic algorithms (ciphers). If S-box does not possess good properties, a cipher would be susceptible to attacks. To design suitable S-boxes, we can use heuristics as it allows significant freedom in the selection of required cryptographic properties. Unfortunately, with heuristics, one is seldom sure how good a trade-off between cryptographic properties is reached or if optimizing for one property optimizes implicitly for another property. In this paper, we consider what is to the best of our knowledge, the most detailed analysis of trade-offs among S-box cryptographic properties. More precisely, we ask questions if one property is optimized, what is the worst possible value for some other property, and what happens if all properties are optimized. Our results show that while it is possible to reach a large variety of possible solutions, optimizing for a certain property would commonly result in good values for other properties. In turn, this suggests that a single-objective approach should be a method of choice unless some precise values for multiple properties are needed.

We investigate whether it is possible to evolve cryptographically strong S-boxes that have additional constraints on their structure. We investigate two scenarios: where S-boxes additionally have a specific sum of values in rows, columns, or diagonals and the scenario where we check that the difference between the Hamming weights of inputs and outputs is minimal. The first case represents an interesting benchmark problem, while the second one has practical ramifications as such S-boxes could offer better resilience against side-channel attacks. We explore three solution representations by using the permutation, integer, and cellular automata-based encoding. Our results show that it is possible to find S-boxes with excellent cryptographic properties (even optimal ones) and reach the required sums when representing S-box as a square matrix. On the other hand, for the most promising S-box representation based on trees and cellular automata rules, we did not succeed in finding S-boxes with small differences in the Hamming weights between the inputs and outputs, which opens an interesting future research direction. Our results for this scenario and different encodings inspired a mathematical proof that the values reached by evolutionary algorithms are the best possible ones.

In this paper, we try to combine the best from the world of heuristics and algebraic constructions for the design of S-boxes: we evolve algebraic constructions that produce S-boxes with as low as possible differential uniformity. Our approach is novel yet very simple and is allowing us to obtain constructions valid for any S-box size of practical interest.

In this paper, we use evolutionary algorithm to evolve customized quantum key distribution (QKD) protocols designed to counter attacks against the system in order to optimize the speed of the secure communication. This is in contrast to most work in QKD protocols, where a fixed protocol is designed and then its security is analyzed to determine how strong an attack it can withstand. We show that our system is able to find protocols that can operate securely against attacks where ordinary QKD protocols would fail. Our algorithm evolves protocols as quantum circuits, thus making the end result potentially easier to implement in practice.

Bent Boolean functions play an important role in the design of secure symmetric ciphers, since they achieve the maximum distance from affine functions allowed by Parseval’s relation. Hyper-bent functions, in turn, are those bent functions which additionally reach maximum distance from all bijective monomial functions, and provide further security towards approximation attacks. Being characterized by a stricter definition, hyper-bent functions are rarer than bent functions, and much more difficult to construct. In this paper, we employ several evolutionary algorithms in order to evolve hyper-bent Boolean functions of various sizes. Our results show that hyper-bent functions are extremely difficult to evolve, since we manage to find such functions only for the smallest investigated size. Interestingly, we are able to identify this difficulty as not lying in the evolution of hyper-bent functions itself, but rather in evolving some of their components, i.e. bent functions. Finally, we present an additional parameter to evaluate the performance of evolutionary algorithms when evolving Boolean functions: the diversity of the obtained solutions.

Substitution Boxes (S-boxes) are nonlinear objects often used in the design of cryptographic algorithms. The design of high quality S-boxes is an interesting problem that attracts a lot of attention. Many attempts have been made in recent years to use heuristics to design S-boxes, but the results were often far from the previously known best obtained ones. Unfortunately, most of the effort went into exploring different algorithms and fitness functions while little attention has been given to the understanding why this problem is so difficult for heuristics. In this paper, we conduct a fitness landscape analysis to better understand why this problem can be difficult. Among other, we find that almost each initial starting point has its own local optimum, even though the networks are highly interconnected.

Finding the shortest addition chain for a given exponent is a significant problem in cryptography. In this work, we present a genetic algorithm with a novel encoding of solutions and new crossover and mutation operators to minimize the length of the addition chains corresponding to a given exponent. We also develop a repair strategy that significantly enhances the performance of our approach. The results are compared with respect to those generated by other metaheuristics for exponents of moderate size, but we also investigate values up to 2 ²⁵⁵- 21. For numbers of such size, we were unable to find any results produced by other metaheuristics which could be used for comparison purposes. Therefore, we decided to add three additional strategies to serve as benchmarks. Our results indicate that the proposed approach is a very promising alternative to deal with this problem. We also consider a more practical perspective by taking into account the implementation cost of the chains: we optimize the addition chains with regards to the type of operations as well as the number of instructions required for the implementation.

Boolean functions have a prominent role in many real-world applications, which makes them a very active research domain. Throughout the years, various heuristic techniques proved to be an attractive choice for the construction of Boolean functions with different properties. One of the most important properties is nonlinearity, and in particular maximally nonlinear Boolean functions are also called bent functions. In this paper, instead of considering Boolean functions, we experiment with quaternary functions. The corresponding problem is much more difficult and presents an interesting benchmark as well as realworld applications. The results we obtain show that evolutionary metaheuristics, especially genetic programming, succeed in finding quaternary functions with the desired properties. The obtained results in the quaternary domain can also be translated into the binary domain, in which case this approach compares favorably with the state-of-the-art in Boolean optimization. Our techniques are able to find quaternary bent functions for up to 8 inputs, which corresponds to obtaining Boolean bent functions of 16 inputs.

Orthogonal Arrays (OA) represent an interesting breed of combinatorial designs that finds applications in several domains such as statistics, coding theory, and cryptography. In this work, we address the problem of constructing binary OA through evolutionary algorithms, an approach which received little attention in the combinatorial designs literature. We focus on the representation of a feasible solution, which we encode as a set of Boolean functions whose truth tables are used as the columns of a binary matrix, and on the design of an appropriate fitness function and variation operators for this problem. We finally present experimental results obtained with genetic algorithms (GA) and genetic programming (GP) on optimizing such fitness function, and compare the performances of these two metaheuristics with respect to the size of the considered problem instances. The experimental results show that GP outperforms GA at handling this type of problem, as it converges to an optimal solution in all considered problem instances but one.

Decision tree algorithms are very popular in the area of data mining since the algorithms have a simple inference mechanism and provide a comprehensible way to represent the model. Over the past years, fuzzy decision tree algorithms have been proposed in order to handle the uncertainty in the data. Fuzzy decision tree algorithms have shown to outperform classical decision tree algorithms. This chapter investigates a fuzzy decision tree algorithm applied to the classification of gene expression data. The fuzzy decision tree algorithm is compared to a classical decision tree algorithm as well as other well-known data mining algorithms commonly applied to classification tasks. Based on the five data sets analyzed, the fuzzy decision tree algorithm outperforms the classical decision tree algorithm. However, compared to other commonly used classification algorithms, both decision tree algorithms are competitive, but they do not reach the accuracy values of the best performing classifier. One of the advantages of decision tree models including the fuzzy decision tree algorithm is however the simplicity and comprehensibility of the model as demonstrated in the chapter.

Finding cryptographic primitives satisfying certain properties is a difficult problem. In this domain, besides the algebraic constructions, researchers often use heuristics. There exists a set of interesting problems related to the notion of differential uniformity for a function F: F2n→ F2m. When n=m, then the best obtainable differential uniformity equals 2, since it is necessarily positive and even, and since examples of differentially 2-uniform functions are known. Heuristics are able to reach such functions; there is then some intuition that heuristics can be used for other open problems related to differential uniformity. When n > m > n/2, differential uniformity is bounded by 2n-m+2 from below (when m=n-2, by 6). Unfortunately, we know such functions only for dimensions equal to n=4,5. In this paper, we explore several evolutionary algorithms and problem sizes in order to find functions having differential uniformity equal to 6. Our results show that several solution encodings are able to find such functions but only in dimensions (4, 2) and (5, 3). Since differentially 6-uniform functions were known for those sizes before, our results can be used as a source of new functions in those dimensions and as an indicator that for (6, 4) such functions either do not exist or that it is extremely difficult to find them.

We investigate the design of Orthogonal Latin Squares (OLS) by means of Genetic Algorithms (GA) and Genetic Programming (GP). Since we focus on Latin squares generated by Cellular Automata (CA), the problem can be reduced to the search of pairs of Boolean functions that give rise to OLS when used as CA local rules. As it is already known how to design CA-based OLS with linear Boolean functions, we adopt the evolutionary approach to address the nonlinear case, experimenting with different encodings for the candidate solutions. In particular, for GA we consider single bitstring, double bitstring and quaternary string encodings, while for GP we adopt a double tree representation. We test the two metaheuristics on the spaces of local rules pairs with n = 7 and n = 8 variables, using two fitness functions. The results show that GP is always able to generate OLS, even if the optimal solutions found with the first fitness function are mostly linear. On the other hand, GA achieves a remarkably lower success rate than GP in evolving OLS, but the corresponding Boolean functions are always nonlinear.