ON BOOLEAN BENT FUNCTIONS AND THEIR GENERALIZATIONS

Abstract

In this thesis, we investigate and analyze a special class of Boolean functions namely bent functions. Using the existing techniques we derive the lower bounds of second-order nonlinearity and identify the a ne inequivalent classes of bent functions. We further construct some classes of generalized bent functions. We identify some classes of Boolean functions having maximum possible second-order nonlinearity by using Gowers norm. A class of cubic Maiorana{McFarland (M) bent functions having no a ne derivative was constructed by Canteaut and Charpin [5], thereby solving an open problem posed by Hou [149]. We construct two classes of cubic M bent functions with no a ne derivative and show their mutual a ne inequivalence. Two (so-called C;D) classes of permutation-based bent Boolean functions were introduced by Carlet [17] two decades ago, but without specifying some explicit construction methods for their construction (apart from the subclass D0). We look in more detail at the C class, and derive some existence and nonexistence results concerning the bent functions in the C class for many of the known classes of permutations over F2n. Most importantly, the existence results induce generic methods of constructing bent functions in class C which possibly do not belong to the completed Maiorana{McFarland class. The question whether the speci c permutations and related subspaces we identify in this article indeed give bent functions outside the completed Maiorana{McFarland class remains open. In 1985, Kumar et al. [98] introduced the concept of generalized bent functions f : Zn q 􀀀! Zq where q > 1 is a positive integer and A. C. Ambrosimov [4] proposed another generalized bent functions over nite eld. We consider functions from Fn p to Fp, and characterize the subspace sum concept (depending upon the derivative) and give many of its properties. In particular, it is shown that the subspace sum is an a ne invariant. Further, we construct two new classes of generalized bent functions (so-called Dp, Dp 0 and Cp where Dp 0 is a subclass i of Dp). Also, we prove that the generalized Maiorana{McFarland bent functions and Dp do not contain one another, and derive some existence and nonexistence results concerning the bent functions in the Cp class for many of the known classes of permutations over Fn p . Carlet [28] introduced a recursive lower bound on nonlinearity pro le of Boolean functions. We construct a class of cubic Maiorana{McFarland bent-negabent functions by using Feistel functions and then obtain the lower bound of their second-order nonlinearities. Gowers [126] introduced a new measure of functions which is called Gowers uniformity norm. The Gowers U3 norm of a Boolean function is the measure of its resistance to quadratic approximations. We compute Gowers U3 norms for some classes of Maiorana{ McFarland bent functions. In particular, we explicitly determine the value of the Gowers U3 norm of Maiorana{McFarland bent functions obtained by using APN permutations. Further, it is proved that this value is always smaller than the Gowers U3 norms of Maiorana{ McFarland bent functions obtained by using di erentially -uniform permutations, for all 4. We compute the Gowers U3 norm for a class of cubic monomial functions, not necessarily bent, and show that for n = 6, these norm values are less than that obtained for Maiorana{McFarland bent function constructed by using APN permutations. Further, we computationally show that there exist 6-variable functions in this class which are not bent but achieve the maximum second-order nonlinearity for 6 variables.