Random numbers (in one sense or another) have applications in computer simulation, Monte Carlo integration, cryptography, randomized computation, radar ranging, and other areas. It is impractical to generate random numbers in real life, instead sequences of numbers (or of bits) that appear to be ``random" yet repeatable are used in real life applications. These sequences are called pseudorandom sequences. To determine the suitability of pseudorandom sequences for applications, we need to study their properties, in particular, their statistical properties. The simplest property is the minimal period of the sequence. That is, the shortest number of steps until the sequence repeats. One important type of pseudorandom sequences is the sequences generated by feedback with carry shift registers (FCSRs). In this dissertation, we study statistical properties of N-ary FCSR sequences with odd prime connection integer q and least period (q-1)/2. These are called half-ℓ-sequences. More precisely, our work includes: The number of occurrences of one symbol within one period of a half-ℓ-sequence; The number of pairs of symbols with a fixed distance between them within one period of a half-ℓ-sequence; The number of triples of consecutive symbols within one period of a half-ℓ-sequence. In particular we give a bound on the number of occurrences of one symbol within one period of a binary half-ℓ-sequence and also the autocorrelation value in binary case. The results show that the distributions of half-ℓ-sequences are fairly flat. However, these sequences in the binary case also have some undesirable features as high autocorrelation values. We give bounds on the number of occurrences of two symbols with a fixed distance between them in an ℓ-sequence, whose period reaches the maximum and obtain conditions on the connection integer that guarantee the distribution is highly uniform. In another study of a cryptographically important statistical property, we study a generalization of correlation immunity (CI). CI is a measure of resistance to Siegenthaler's divide and conquer attack on nonlinear combiners. In this dissertation, we present results on correlation immune functions with regard to the q-transform, a generalization of the Walsh-Hadamard transform, to measure the proximity of two functions. We give two definitions of q-correlation immune functions and the relationship between them. Certain properties and constructions for q-correlation immune functions are discussed. We examine the connection between correlation immune functions and q-correlation immune functions.

In this thesis, we work on the upper bound for nonlinearity of t-resilient Boolean functions given by Sarkar and Maitra, which is based on divisibility properties of spectral weights of resilient functions and study construction methods that achieve the upper bound. One of the construction methods, introduced by Maity and Johansson, starts with a bent function and complements some values of its truth table corresponding to a previously chosen set of inputs, S, which satisfies three criteria. In this thesis, we show that a fourth criterion is needed for t-resiliency of the resulting function, and prove that three criteria of Maity and Johansson do not guarantee resiliency. We also work on other constructions, one by Sarkar and Maitra, which uses a Maiorana-McFarland like technique to satisfy the upper bound and the other by Tarannikov, which satisfies the nonlinearity bound using a technique with low computational complexity. However, these methods have tendency to maximize the order of resiliency for a given number of variables, therefore one cannot construct functions for all possible resiliency values given the number of variables, using this method. We further go into details and compute the auto-correlation functions of the constructed Boolean functions to find the absolute indicator and sum-of-squared-errors for each of them. We also provide a comparison of Boolean functions constructed by other techniques given in the literature, together with the ones studied in this thesis.

Fundamental to the electronic security of information and communication systems, is the correct use and application of appropriate ciphers. The strength of these ciphers, particularly in their ability to resist cryptanalytic attacks, directly in uences the overall strength of the entire system. The strength of the underlying cipher is reliant upon a robust structure and the carefully designed interaction between components in its architecture. Most importantly, however, cipher strength is critically dependent on the strength of the individual components of which it is comprised. Boolean functions and substitution boxes (s-boxes) are among the most common and essential components of ciphers. This is because they are able to provide a cipher with strengthening properties to resist known and potential cryptanalytic attacks. Thus, it is not surprising that significant research effort has been made in trying to develop ways of obtaining boolean functions and substitution boxes with optimal achievable measures of desirable cryptographic properties. Three of the main cryptographic properties required by strong boolean functions and s-boxes are nonlinearity, correlation immunity and propagation criteria, with different cryptographic applications requiring different acceptable measures of these and other properties. As combinations of cryptographic properties exhibited by functions can be conicting, finding cryptographically strong functions often means that a trade-off needs to be made when optimizing property values. Throughout this thesis, the term "optimization" specifically refers to seeking to obtain the best achievable combination of target property values which may be exhibited by boolean functions and s-boxes, regardless of whether the relevant properties are conflicting or complementary. This thesis focusses on a particular class of techniques for obtaining strong functions for cryptographic applications, referred to as heuristic methods or, simply, heuristics. Three new heuristic methods, each aimed at generating boolean functions optimizing one or more of the main cryptographic properties mentioned above, in addition to other desirable properties, are presented. The first of the new heuristic methods developed for this thesis focusses on generating boolean functions which are balanced and exhibit very high nonlinearities. Highly nonlinear balanced functions are critical to many cryptographic applications, as they provide good resistance to linear cryptanalytic attacks. This first method is based on the recursive modification of a starting bent function and is shown to be highly successful and efficient at generating numerous such functions, which also exhibit low autocorrelation values, in a very short computational time. The generation of balanced, correlation immune boolean functions that also exhibit the confl icting property of high nonlinearity is the focus of the second new heuristic method developed for this thesis. By concatenating selected pairs of lower-dimensional boolean functions together in the Walsh Hadamard transform domain, direct optimization for both resilience and nonlinearity was able to take place at each level towards and for the final function. This second method was able to generate examples of boolean functions with almost all of the best known optimal combinations of target property values. Experiments have shown the success of this method in consistently generating highly nonlinear resilient boolean functions, for a range of orders of resilience, with such functions possessing optimal algebraic degree. A third new heuristic method, which searches for balanced boolean functions which satisfy a non-zero degree of propagation criteria and exhibit high nonlinearity, is presented. Intelligent bit manipulations in the truth table of starting functions, based on fundamental relationships between boolean function transforms and measures, provide the design rationale for this method. Two new function generation schemes have been proposed for this method, to efficiently satisfy the requirements placed on the starting functions utilized in the computational process. An optional process attempts to increase the algebraic degree of the resulting functions, without sacrificing the optimalities that are achievable. The validity of this method is demonstrated through the success of various experimental trials. Switching the focus from single output boolean functions to multiple output boolean functions (s-boxes), the effectiveness of existing heuristic techniques (namely Genetic Algorithm, Hill Climbing Method and combined Genetic Algorithm/Hill Climbing) in primarily being applied to improve the nonlinearity of s-boxes of various dimensions, is investigated. The prior success of these heuristic techniques for improving the nonlinearity of boolean functions has been previously demonstrated, as has the success of hill climbing in isolation when applied to bijective s-boxes. An extension to the bijective s-box optimization work is presented in this thesis. In this new research, a Genetic Algorithm, Hill Climbing Method and the two in combination are applied to the nonlinearity and autocorrelation optimization of regular NxM s-boxes (N > M) to investigate the effectiveness and efficiency of each of these heuristics. A new breeding scheme, utilized in the Genetic Algorithm and combined Genetic Algorithm/Hill Climbing trials, is also presented. The success of experimental results compared to random regular s-box generation is demonstrated. New research in applying the Hill Climbing Method to construct NxM sboxes (N > M) required to meet specific property criteria is presented. The consideration of the characteristics desired by the constructed s-boxes largely dictated the generation process. A discussion on the generation process of the component functions is included. Part of the results produced by experimental trials were incorporated into a commonly used family of stream ciphers, thus further supporting the use of heuristic techniques as a useful means of obtaining strong functions suitable for incorporation into practical ciphers. An analysis of the cryptographic properties of the s-box used in the MARS block cipher, the method of generation and the computational time taken to obtain this s-box, led to the new research reported in this thesis on the generation of MARS-like s-boxes. It is shown that the application of the Hill Climbing Method, with suitable requirements placed on the component boolean functions, was able to generate multiple MARS-like s-boxes which satisfied the MARS sbox requirements and provided additional properties. This new work represented an alternative approach to the generation of s-boxes satisfying the MARS sbox property requirements but which are cryptographically superior and can be obtained in a fraction of the time than that which was taken to produce the MARS s-box. An example MARS-like s-box is presented in this thesis. The overall value of heuristic methods in generating strong boolean functions and substitution boxes is clearly demonstrated in this thesis. This thesis has made several significant contributions to the field, both in the development of new, specialized heuristic methods capable of generating strong boolean functions, and in the analysis and optimization of substitution boxes, the latter achieved through applying existing heuristic techniques.

Boolean functions are accepted to be cryptographically strong if they satisfy some common pre-determined criteria. It is expected that any design criteria should remain invariant under a large group of transformations due to the theory of similarity of secrecy systems proposed by Shannon. One of the most important design criteria for cryptographically strong Boolean functions is the nonlinearity criterion. Meier and Staffelbach studied nonlinearity preserving transformations, by considering the invertible transformations acting on the arguments of Boolean functions, namely the pre-transformations. In this thesis, first, the results obtained by Meier and Staffelbach are presented. Then, the invertible transformations acting on the truth tables of Boolean functions, namely the post-transformations, are studied in order to determine whether they keep the nonlinearity criterion invariant. The equivalent counterparts of Meier and Staffelbach&rsquo / s results are obtained in terms of the post-transformations. In addition, the existence of nonlinearity preserving post-transformations, which are not equivalent to pre-transformations, is proved. The necessary and sufficient conditions for an affine post-transformation to preserve nonlinearity are proposed and proved. Moreover, the sufficient conditions for an non-affine post-transformation to keep nonlinearity invariant are proposed. Furthermore, it is proved that the smart hill climbing method, which is introduced to improve nonlinearity of Boolean functions by Millan et. al., is equivalent to applying a post-transformation to a single Boolean function. Finally, the necessary and sufficient condition for an affine pre-transformation to preserve the strict avalanche criterion is proposed and proved.

A Boolean function can be represented in several different forms. These different representation have advantages and disadvantages of their own. The Algebraic Normal Form, truth table, and Walsh spectrum representations are widely studied in literature. In 1999, Claude Carlet and Phillippe Guillot introduced the Numerical Normal Form. NumericalNormal Form(NNF) of a Boolean function is similar to Algebraic Normal Form, with integer coefficients instead of coefficients from the two element field. Using NNF representation, just like the Walsh spectrum, characterization of several cryptographically important functions, such as resilient and bent functions, is possible. In 2002, Carlet had shown several divisibility results concerning resilient and correlation-immune functions using NNF. With these divisibility results, Carlet is able to give bounds concerning nonlinearity of resilient and correlation immune functions. In this thesis, following Carlet and Guillot, we introduce the Numerical Normal Form and derive the pairwise relations between the mentioned representations. Characterization of Boolean, resilient and bent functions using NNF is also given. We then review the divisibility results of Carlet, which will be linked to some results on the nonlinearity of resilient and correlation immune functions. We show the M&ouml / bius inversion properties of NNF of a Boolean function, using Gian-Carlo Rota&rsquo / s work as a guide. Finally, using a lot of the mentioned results, we prove a necessary condition on theWalsh spectrum of Boolean functions with given degree.