This chapter provides a general overview of AI methods used to support the design of cryptographic primitives and protocols. After giving a brief introduction to the basic concepts underlying the field of cryptography, we review the most researched use cases concerning the use of AI techniques and models to design cryptographic primitives, focusing mainly on Boolean functions, S-boxes and pseudorandom number generators. We then point out two interesting directions for further research on the design of cryptographic primitives where AI methods could be applied in the future.

We investigate the use of Genetic Programming (GP) as a convolutional predictor for missing pixels in images. The training phase is performed by sweeping a sliding window over an image, where the pixels on the border represent the inputs of a GP tree. The output of the tree is taken as the predicted value for the central pixel. We consider two topologies for the sliding window, namely the Moore and the Von Neumann neighborhood. The best GP tree scoring the lowest prediction error over the training set is then used to predict the pixels in the test set. We experimentally assess our approach through two experiments. In the first one, we train a GP tree over a subset of 1000 complete images from the MNIST dataset. The results show that GP can learn the distribution of the pixels with respect to a simple baseline predictor, with no significant differences observed between the two neighborhoods. In the second experiment, we train a GP convolutional predictor on two degraded images, removing around 20% of their pixels. In this case, we observe that the Moore neighborhood works better, although the Von Neumann neighborhood allows for a larger training set.

Boolean functions have numerous applications in domains as diverse as coding theory, cryptography, and telecommunications. Heuristics play an important role in the construction of Boolean functions with the desired properties for a specific purpose. However, there are only sparse results trying to understand the problem's difficulty. With this work, we aim to address this issue. We conduct a fitness landscape analysis based on Local Optima Networks (LONs) and investigate the influence of different optimization criteria and variation operators. We observe that the naive fitness formulation results in the largest networks of local optima with disconnected components. Also, the combination of variation operators can both increase or decrease the network size. Most importantly, we observe correlations of local optima's fitness, their degrees of interconnection, and the sizes of the respective basins of attraction. This can be exploited to restart algorithms dynamically and influence the degree of perturbation of the current best solution when restarting.

Reversible Cellular Automata (RCA) are a particular kind of shift-invariant transformations characterized by dynamics composed only of disjoint cycles. They have many applications in the simulation of physical systems, cryptography, and reversible computing. In this work, we formulate the search of a specific class of RCA – namely, those whose local update rules are defined by conserved landscapes – as an optimization problem to be tackled with Genetic Algorithms (GA) and Genetic Programming (GP). In particular, our experimental investigation revolves around three different research questions, which we address through a single-objective, a multi-objective, and a lexicographic approach. In the single-objective approach, we observe that GP can already find an optimal solution in the initial population. This indicates that evolutionary algorithms are not needed when evolving only the reversibility of such CA, and a more efficient method is to generate at random syntactic trees that define the local update rule. On the other hand, GA and GP proved to be quite effective in the multi-objective and lexicographic approach to (1) discover a trade-off between the reversibility and the Hamming weight of conserved landscape rules, and (2) observe that conserved landscape CA cannot be used in symmetric cryptography because their Hamming weight (and thus their nonlinearity) is too low.

This paper investigates the influence of genotype size on evolutionary algorithms' performance. We consider genotype compression (where genotype is smaller than phenotype) and expansion (genotype is larger than phenotype) and define different strategies to reconstruct the original variables of the phenotype from both the compressed and expanded genotypes. We test our approach with several evolutionary algorithms over three sets of optimization problems: COCO benchmark functions, modeling of Physical Unclonable Functions, and neural network weight optimization. Our results show that genotype expansion works significantly better than compression, and in many scenarios, outperforms the original genotype encoding. This could be attributed to the change in the genotype-phenotype mapping introduced with the expansion methods: this modification beneficially transforms the domain landscape and alleviates the search space traversal.

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.

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.

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.

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.

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.

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.

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.

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.

In this paper, we ask a question whether evolutionary algorithms can evolve cryptographic algorithms when no precise design criteria are given. Our strategy utilizes Cartesian Genetic Programming in the bi-level optimization setting with multiple populations trying to evolve a cryptographic algorithm and break it. To challenge our design paradigm, we consider a number of scenarios with varying criteria on the system and its security. We are able to obtain interesting results in several scenarios where the attacker is not able to understand the text with more than a random chance. Interestingly, our system is able to develop various versions of one-time pads, which are the only systems that ensure perfect secrecy. Although our system is far from practical, we consider it interesting since it gives good results that are also human-readable.

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.

Cellular Automata (CA) represent an interesting approach to design Substitution
Boxes (S-boxes) having good cryptographic properties and low implementation costs. From the cryptographic perspective, up to now there have been only ad-hoc studies about specific kinds of CA, the best known example being the χ nonlinear transformation used in Keccak. In this paper, we undertake a systematic investigation of the cryptographic properties of S-boxes defined by CA, proving some upper bounds on their nonlinearity and differential
uniformity. Next, we extend some previous published results about the construction of CAbased S-boxes by means of a heuristic technique, namely Genetic Programming (GP). In particular, we propose a “reverse engineering” method based on De Bruijn graphs to determine whether a specific S-box is expressible through a single CA rule. Then, we use GP to assess if some CA-based S-box with optimal cryptographic properties can be described
by a smaller CA. The results show that GP is able to find much smaller CA rules defining the same reference S-boxes up to the size 7 × 7, suggesting that our method could be used to find more efficient representations of CA-based S-boxes for hardware implementations. Finally, we classify up to affine equivalence all 3 × 3 and 4 × 4 CA-based S-boxes.

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.

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.

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.