ON HIGHER-ORDER NONLINEARITIES OF BOOLEAN FUNCTIONS

Abstract

This thesis presents an investigation on the higher-order nonlinearities and the non-linearity profiles of some classes of Boolean functions. The idea of nonlinearity is generalized to higher-order nonlinearity and nonlinearity profile of a Boolean function. Our goal is to identify classes of Boolean functions which show good behaviour with respect to higher-order nonlinearities. In 2008 Carlet introduced a recursive method for the computation of lower bounds of higher-order nonlinearities of Boolean func-tions and using this approach he obtained lower bounds of higher-order nonlinearities for several classes of Boolean functions. We present a study in this direction, using the recursive approach of Carlet we identify classes or subclasses of functions whose lower bounds of the second-order (or the third-order) nonlinearities are better than some previously known general lower bounds for the second-order (or the third-order) nonlinearities and in some cases we determine subclasses of cubic functions with the largest known second-order nonlinearity. Our results indicate that there are subclasses of functions whose lower bounds on the higher-order nonlinearities are much larger than the general lower bounds obtained by Carlet. 1 First we deduce lower bounds on the second-order nonlinearities of two classes of cubic Boolean functions. Both these classes possess no affine derivative and contain bent functions. These bent functions belong to the class of Maiorana-McFarland type bent functions of algebraic degree 3. A general lower bound of the second-order non-linearities of the cubic functions which have no affine derivative has been deduced by Carlet in 2008. The bounds obtained by us for the above classes are larger than the __ general -bound. obtained by Cadet. Direct compiita.tion using the algorithm of Fourquet and Tavernier shows that for the case n = 10 some functions in these classes have the largest known second-order nonlinearity which is 400. Next we investigate the lower bounds of the second-order nonlinearities of a subclass of cubic monomial functions of the form Tr( μx2y+2'+1), where i and j are integers such that n > i > j > 0 and μ E Fen . The obtained bounds are valid for n> 2i. Our results provide information related to the choice of i for which these functions possess high second-order nonlinearities. In some cases our bounds are better than the general lower bound obtained by Carlet for cubic functions and the bounds of some other classes of Boolean functions which are recently studied. We study the third-order nonlinearities of a subclass of Kasami functions of the form Tr' (/x57). A general lower bound on the higher-order nonlinearities of Kasami functions has been obtained by Carlet for odd values of n. We deduce lower bounds on the third-order nonlinearities of Tr( x57) for all values of n, our bounds improve upon the general bound for n > 12. Our results combined with the computational results of Fourquet and Tavernier give information related to the nonlinearity profile ii ofTri(x57) for n=7,8,10. We analyze a special case of an existing construction of cubic Boolean functions for second-order nonlinearities. The construction was given by Leander and McGuire in 2009, which produces a class of cubic bent functions on n variables by concatenating quadratic Gold functions on n —1 variables. We observe that these cubic bent functions have high second-order nonlinearities. For n = 8 the lower bound of the second-order nonlinearities of these functions achieves the largest known value of second-order nonlinearity which is 84. Thus we identify a class of cubic functions with reasonably good nonlinearity profile. Finally, we determine the lower bounds of the second-order nonlinearities of some 6-variable and the third-order nonlinearities of some 8-variable monomial partial spreads type Boolean functions respectively. iii