A STUDY OF SOME CRYPTOGRAPHICALLY SIGNIFICANT BOOLEAN FUNCTIONS AND THEIR GENERALIZATIONS

Abstract

This thesis presents an investigation on some cryptographic properties of Boolean functions, q-ary functions due to Kumar et al. (1985) de ned from Zn q to Zq, and the functions from Zn q to Z2q. Our aim is to identify and to construct cryptographically signi cant functions which show good behavior with respect to some important cryptographic criteria including balancedness, resiliency, nonlinearity, crosscorrelation, autocorrelation and global avalanche characteristics (GAC). We identify some classes of Boolean functions with high nonlinearity which show good behavior with respect to second order nonlinearity. We investigate several properties of q-ary functions in terms of their Walsh-Hadamard transform (WHT) and crosscorrelation spectra. The crosscorrelation of a subclass of Maiorana-McFarland (MM) type q-ary bent functions is obtained. Some constructions of q-ary balanced functions which have good GAC measured in terms of the indicators: the sum-of-squares-of-modulus indicator (SSMI) and the modulus indicator (MI), and which satisfy propagation criteria (PC), are presented. We present a new generalization of negabent functions by considering the functions Zn q to Z2q. We investigate several properties of generalized negabent functions and provide some examples of such functions. In 2008 Carlet has introduced a recursive method for the computation of lower bounds of higher order nonlinearities of Boolean functions. Using Carlet's recursive approach we identify some classes of highly nonlinear Boolean functions whose lower bounds on second order nonlinearities are better than some previously known general bounds. We have considered the problem of computing lower bounds on second order nonlinearities of cubic monomial functions of the form (i) f(x) = trn 1 ( x22r+2r+1+1); where n = 3r; 5r and 2 Z2n n f0g, (ii) f(x) = trn 1 ( x22r+2r+1); where n = 3r and 2 Z2r n f0g. Boolean functions in these classes possess no a ne derivatives. The general lower bounds on second i order nonlinearities of the cubic Boolean functions which have no a ne derivative have been deduced by Carlet [15]. The bounds obtained by us for the above classes of functions are better than the general bounds obtained by Carlet [15] and the bounds of some other classes of Boolean functions which are recently studied [50, 53, 147]. Further, we obtain lower bounds on second order nonlinearities for some classes of cubic Boolean functions based on secondary constructions. Gao et al. [52] have provided a method for the construction of plateaued resilient functions with disjoint spectra. Using this approach, we provide some new constructions of highly nonlinear resilient Boolean functions on large number of variables with disjoint spectra by concatenating disjoint spectra resilient functions on small number of variables. In some cases the nonlinearity bounds of the constructed functions are better than the bounds obtained in [52]. Several results on q-ary functions in terms of their WHT and crosscorrelation spectra are presented. We obtain the crosscorrelation of a subclass of Maiorana-McFarland (MM) type q-ary bent functions. A characterization of quaternary (4-ary) bent functions on n+1 variables in terms of their subfunctions on n variables is presented. We slightly generalize a result of Tokareva [151] by proving that the direct sum of two q-ary bent functions f1 and f2 is a q-ary bent function if and only if f1 and f2 both are q-ary bent. Analogous to the indicators, the sum-of-squares indicator and the absolute indicator in Boolean case, we de ne two similar indicators: the sum-of-squares-of-modulus indicator (SSMI) f;g and the modulus indicator (MI) 4f;g to measure the global avalanche characteristics (GAC) of two q-ary functions. We study q-ary functions in terms of these two indicators and derive some lower and upper bounds on these indicators. Also, we provide some constructions of balanced quaternary functions with high nonlinearity under the Lee metric. Further, we present construction of two classes of q-ary balanced functions which have good GAC measured in terms of two indicators, the SSMI and the MI, and satisfy PC. It is shown that the cryptographic criteria the SSMI, MI, and PC of q-ary functions are invariant under a ne transformations. Also, we give a construction of q-ary s-plateaued functions and obtain their SSMI. We provide a relationship between the autocorrelation spectrum of a cubic Boolean function and the dimension of the kernel of the bilinear form associated ii with its derivative. Using this result, we identify several classes of cubic semi-bent Boolean functions which have good bounds on their SSMI and MI, and hence show good behavior with respect to the GAC. We present a method for the construction of ternary functions on (n + 1)-variables by using decomposition functions f1; f2; f3 on n-variables, and investigate a link between the SSMI of an (n + 1)-variable ternary function f and the SSMI of their n-variable decomposition functions f1; f2; f3. Also, we provide a construction of ternary functions with low value of SSMI by using pairwise perfectly uncorrelated m-plateaued ternary functions and modi ed ternary bent functions. A relationship among the indicators, f;g, f (the SSMI of f) and g of two q-ary functions f and g is obtained. Further, we deduce upper bounds to the indicators the SSMI and the MI of two q-ary functions for the case that one of them is s-plateaued q-ary function. We propose a new generalization of negabent functions by considering the functions from Zn q to Z2q: We investigate several properties of generalized nega-Hadamard transform (GNHT) and its behavior on various combinations of functions. Some results describing the properties of generalized negabent functions are presented. We have established a connection between the generalized nega-autocorrelation spectra of functions and their GNHT. A characterization of generalized negabent (for q = 4) functions on n+1 variables in terms of their subfunctions on n-variables is presented. Further, in this setup, we present several examples of generalized negabent functions for di erent values of q and n: