Finding nonnormal bent functions

The question if there exist nonnormal bent functions was an open question for several years. A Boolean function in n variables is called normal if there exists an affine subspace of dimension n/2 on which the function is constant. In this paper we give the first nonnormal bent function and even an example for a nonweakly normal bent function. These examples belong to a class of bent functions found in [J.F. Dillon, H. Dobbertin, New cyclic difference sets with Singer parameters, in: Finite Fields and Applications, to appear], namely the Kasami functions. We furthermore give a construction which extends these examples to higher dimensions. Additionally, we present a very efficient algorithm that was used to verify the nonnormality of these functions.     

A new construction of bent functions based on {\mathbb{Z}} -bent functions

Dobbertin has embedded the problem of construction of bent functions in a recursive framework by using a generalization of bent functions called ${\mathbb{Z}}$ -bent functions. Following his ideas, we generalize the construction of partial spreads bent functions to partial spreads ${\mathbb{Z}}$ -bent functions of arbitrary level. Furthermore, we show how these partial spreads ${\mathbb{Z}}$ -bent functions give rise to a new construction of (classical) bent functions. Further, we construct a bent function on 8 variables which is inequivalent to all Maiorana–McFarland as well as PS _ap type bents. It is also shown that all bent functions on 6 variables, up to equivalence, can be obtained by our construction.     

Association schemes arising from bent functions

We give a construction of 3-class and 4-class association schemes from s-nonlinear and differentially 2 ^s -uniform functions, and a construction of p-class association schemes from weakly regular p-ary bent functions, where p is an odd prime.     

A new class of bent and hyper-bent Boolean functions in polynomial forms

Bent functions are maximally nonlinear Boolean functions and exist only for functions with even number of inputs. This paper is a contribution to the construction of bent functions over ${\mathbb{F}_{2^{n}}}$ (n = 2m) having the form ${f(x) = tr_{o(s_1)} (a x^ {s_1}) + tr_{o(s_2)} (b x^{s_2})}$ where o(s _i ) denotes the cardinality of the cyclotomic class of 2 modulo 2 ⁿ ? 1 which contains s _i and whose coefficients a and b are, respectively in ${F_{2^{o(s_1)}}}$ and ${F_{2^{o(s_2)}}}$ . Many constructions of monomial bent functions are presented in the literature but very few are known even in the binomial case. We prove that the exponents s ₁ = 2 ^m ? 1 and ${s_2={\frac {2^n-1}3}}$ , where ${a\in\mathbb{F}_{2^{n}}}$ (a ?? 0) and ${b\in\mathbb{F}_{4}}$ provide a construction of bent functions over ${\mathbb{F}_{2^{n}}}$ with optimum algebraic degree. For m odd, we give an explicit characterization of the bentness of these functions, in terms of the Kloosterman sums. We generalize the result for functions whose exponent s ₁ is of the form r(2 ^m ? 1) where r is co-prime with 2 ^m  + 1. The corresponding bent functions are also hyper-bent. For m even, we give a necessary condition of bentness in terms of these Kloosterman sums.     

Generalized bent functions and their properties

Jet J_q^m denote the set of m-tuples over the integers modulo q and set $\text{i=}\text{?1}$, $\text{w = e}{}^{\mathrm{<mtext>i(</mtext><mtext>2\pi </mtext><mtext>q</mtext><mtext>)</mtext>}}$. As an extension of Rothaus' notion of a bent function, a function f, f: J_q^m → J_q¹ is called bent if all the Fourier coefficients of w^f have unit magnitude. An important feature of these functions is that their out-of-phase autocorrelation value is identically zero. The nature of the Fourier coefficients of a bent function is examined and a proof for the non-existence of bent functions over J_q^m, m odd, is given for many values of q of the form q = 2 (mod 4). For every possible value of q and m (other than m odd and q = 2 (mod 4)), constructions of bent functions are provided.     

Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions

We survey the properties of two parameters introduced by C. Ding and the author for quantifying the balancedness of vectorial functions and of their derivatives. We give new results on the distribution of the values of the first parameter when applied to F + L, where F is a fixed function and L ranges over the set of linear functions: we show an upper bound on the nonlinearity of F by means of these values, we determine then the mean of these values and we show that their maximum is a nonlinearity parameter as well, we prove that the variance of these values is directly related to the second parameter. We briefly recall the known constructions of bent vectorial functions and introduce two new classes obtained with Gregor Leander. We show that bent functions can be used to build APN functions by concatenating the outputs of a bent (n, n/2)-function and of some other (n, n/2)-function. We obtain this way a general infinite class of quadratic APN functions. We show that this class contains the APN trinomials and hexanomials introduced in 2008 by L. Budaghyan and the author, and a class of APN functions introduced, in 2008 also, by Bracken et al.; this gives an explanation of the APNness of these functions and allows generalizing them. We also obtain this way the recently found Edel?CPott cubic function. We exhibit a large number of other sub-classes of APN functions. We eventually design with this same method classes of quadratic and non-quadratic differentially 4-uniform functions.     

On differential uniformity and nonlinearity of functions

We present results related to vectorial plateaued functions and mappings whose derivatives are 2^s-to-1 functions. The results in this note generalize facts about almost perfect nonlinear and almost bent functions. We investigate the connection between plateaued and 2^s-to-1 functions. We show that functions which are both plateaued and differentially uniform give rise to partial difference sets.     

Counting all bent functions in dimension eight 99270589265934370305785861242880

Based on the classification of the homogeneous Boolean functions of degree 4 in 8 variables we present the strategy that we used to count the number of all bent functions in dimension 8. There are $$99270589265934370305785861242880 \approx 2^{106}$$ such functions in total. Furthermore, we show that most of the bent functions in dimension 8 are nonequivalent to Maiorana?CMcFarland and partial spread functions.     

Bent and generalized bent Boolean functions

In this paper, we investigate the properties of generalized bent functions defined on ${\mathbb{Z}_2^n}$ with values in ${\mathbb{Z}_q}$ , where q ≥ 2 is any positive integer. We characterize the class of generalized bent functions symmetric with respect to two variables, provide analogues of Maiorana–McFarland type bent functions and Dillon’s functions in the generalized set up. A class of bent functions called generalized spreads is introduced and we show that it contains all Dillon type generalized bent functions and Maiorana–McFarland type generalized bent functions. Thus, unification of two different types of generalized bent functions is achieved. The crosscorrelation spectrum of generalized Dillon type bent functions is also characterized. We further characterize generalized bent Boolean functions defined on ${\mathbb{Z}_2^n}$ with values in ${\mathbb{Z}_4}$ and ${\mathbb{Z}_8}$ . Moreover, we propose several constructions of such generalized bent functions for both n even and n odd.     

Hyper-bent functions and cyclic codes

Bent functions are those Boolean functions whose Hamming distance to the Reed-Muller code of order 1 equal 2^n-1-2^n/2-1 (where the number n of variables is even). These combinatorial objects, with fascinating properties, are rare. Few constructions are known, and it is difficult to know whether the bent functions they produce are peculiar or not, since no way of generating at random bent functions on 8 variables or more is known.The class of bent functions contains a subclass of functions whose properties are still stronger and whose elements are still rarer. Youssef and Gong have proved the existence of such hyper-bent functions, for every even n. We prove that the hyper-bent functions they exhibit are exactly those elements of the well-known PS_ap class, introduced by Dillon, up to the linear transformations x?δx, . Hyper-bent functions seem still more difficult to generate at random than bent functions; however, by showing that they all can be obtained from some codewords of an extended cyclic code H_n with small dimension, we can enumerate them for up to 10 variables. We study the non-zeroes of H_n and we deduce that the algebraic degree of hyper-bent functions is n/2. We also prove that the functions of class PS_ap are some codewords of weight 2^n-1-2^n/2-1 of a subcode of H_n and we deduce that for some n, depending on the factorization of 2ⁿ-1, the only hyper-bent functions on n variables are the elements of the class , obtained from PS_ap by composing the functions by the transformations x?δx, δ≠0, and by adding constant functions. We prove that non- hyper-bent functions exist for n=4, but it is not clear whether they exist for greater n. We also construct potentially new bent functions for n=12.     

CCZ-equivalence of bent vectorial functions and related constructions

We observe that the CCZ-equivalence of bent vectorial functions over ${{\bf F}_2^n}$ (n even) reduces to their EA-equivalence. Then we show that in spite of this fact, CCZ-equivalence can be used for constructing bent functions which are new up to EA-equivalence and therefore to CCZ-equivalence: applying CCZ-equivalence to a non-bent vectorial function F which has some bent components, we get a function F?? which also has some bent components and whose bent components are CCZ-inequivalent to the components of the original function F. Using this approach we construct classes of nonquadratic bent Boolean and bent vectorial functions.     

The essential dependence of Kasami bent functions on the products of variables

Kasami bent functions have the most complicated properties in the class of algebraic constructions of bent functions. We prove that the degree t Kasami functions have nonzero order t ? 2 derivatives for 4 ≤ t ≤ (n + 3)/3 and nonzero order t ? 3 derivatives for (n + 3)/3 < t ≤ n/2. We establish that the order of essential dependence of Kasami bent functions equals either t ? 2 or t ? 3.     

Enumeration of the bent functions of least deviation from a quadratic bent function

We study a construction of the bent functions of least deviation from a quadratic bent function, describe all these bent functions of 2k variables, and show that the quantity of them is 2 ^k (2¹ + 1) ... (2 ^k + 1). We find some lower bound on the number of the bent functions of least deviation from a bent function of the Maiorana-McFarland class.     

Strongly regular graphs constructed from <Emphasis Type="Italic">p</Emphasis>-ary bent functions

In this paper, we generalize the construction of strongly regular graphs in Tan et al. (J. Comb. Theory, Ser. A 117:668–682, 2010) from ternary bent functions to p-ary bent functions, where p is an odd prime. We obtain strongly regular graphs with three types of parameters. Using certain non-quadratic p-ary bent functions, our constructions can give rise to new strongly regular graphs for small parameters.     

Boolean functions with MacWilliams duality

We introduce a new class of Boolean functions for which the MacWilliams duality holds, called MacWilliams-dual functions, by considering a dual notion on Boolean functions. By using the MacWilliams duality, we prove the Gleason-type theorem on MacWilliams-dual functions. We show that a collection of MacWilliams-dual functions contains all the bent functions and all formally self-dual functions. We also obtain the Pless power moments for MacWilliams-dual functions. Furthermore, as an application, we prove the nonexistence of bent functions in 2n variables with minimum degree n?k for any nonnegative integer k and n ≥ N with some positive integer N under a certain condition.     

Normal Boolean functions

Dobbertin (Construction of bent functions and balanced Boolean functions with high nonlinearity, in: Fast Software Encryption, Lecture Notes in Computer Science, Vol. 1008, Springer, Berlin, 1994, pp. 61–74) introduced the normality of bent functions. His work strengthened the interest for the study of the restrictions of Boolean functions on k-dimensional flats providing the concept of k-normality. Using recent results on the decomposition of any Boolean functions with respect to some subspace, we present several formulations of k-normality. We later focus on some highly linear functions, bent functions and almost optimal functions. We point out that normality is a property for which these two classes are strongly connected. We propose several improvements for checking normality, again based on specific decompositions introduced in Canteaut et al. (IEEE Trans. Inform. Theory, 47(4) (2001) 1494), Canteaut and Charpin (IEEE Trans. Inform. Theory). As an illustration, we show that cubic bent functions of 8 variables are normal.     

Equivalence classes of Niho bent functions

Equivalence classes of Niho bent functions are in one-to-one correspondence with equivalence classes of ovals in a projective plane. Since a hyperoval can produce several ovals, each hyperoval is associated with several inequivalent Niho bent functions. For all known types of hyperovals we described the equivalence classes of the corresponding Niho bent functions. For some types of hyperovals the number of equivalence classes of the associated Niho bent functions are at most 4. In general, the number of equivalence classes of associated Niho bent functions increases exponentially as the dimension of the underlying vector space grows. In small dimensions the equivalence classes were considered in detail.

     

Construction of bent functions via Niho power functions

A Boolean function with an even number n=2k of variables is called bent if it is maximally nonlinear. We present here a new construction of bent functions. Boolean functions of the form f(x)=tr(α₁x^d₁+α₂x^d₂), α₁,α₂,x∈F_2ⁿ, are considered, where the exponents d_i (i=1,2) are of Niho type, i.e. the restriction of x^d_i on F_2^k is linear. We prove for several pairs of (d₁,d₂) that f is a bent function, when α₁ and α₂ fulfill certain conditions. To derive these results we develop a new method to prove that certain rational mappings on F_2ⁿ are bijective.     

Strongly regular graphs associated with ternary bent functions

We prove a new characterization of weakly regular ternary bent functions via partial difference sets. Partial difference sets are combinatorial objects corresponding to strongly regular graphs. Using known families of bent functions, we obtain in this way new families of strongly regular graphs, some of which were previously unknown. One of the families includes an example in [N. Hamada, T. Helleseth, A characterization of some {3v₂+v₃,3v₁+v₂,3,3}-minihypers and some [15,4,9;3]-codes with B₂=0, J. Statist. Plann. Inference 56 (1996) 129-146], which was considered to be sporadic; using our results, this strongly regular graph is now a member of an infinite family. Moreover, this paper contains a new proof that the Coulter-Matthews and ternary quadratic bent functions are weakly regular.     

Duality between bent functions and affine functions

A Boolean function in an even number of variables is called bent if it is at the maximal possible Hamming distance from the class of all affine Boolean functions. We prove that there is a duality between bent functions and affine functions. Namely, we show that affine function can be defined as a Boolean function that is at the maximal possible distance from the set of all bent functions.