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.     

Relation between o-equivalence and EA-equivalence for Niho bent functions

Boolean functions, and bent functions in particular, are considered up to so-called EA-equivalence, which is the most general known equivalence relation preserving bentness of functions. However, for a special type of bent functions, so-called Niho bent functions there is a more general equivalence relation called o-equivalence which is induced from the equivalence of o-polynomials. In the present work we study, for a given o-polynomial, a general construction which provides all possible o-equivalent Niho bent functions, and we considerably simplify it to a form which excludes EA-equivalent cases. That is, we identify all cases which can potentially lead to pairwise EA-inequivalent Niho bent functions derived from o-equivalence of any given Niho bent function. Furthermore, we determine all pairwise EA-inequivalent Niho bent functions arising from all known o-polynomials via o-equivalence.     

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.     

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.     

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.     

A novel algorithm enumerating bent functions

Based on the relationship between the Walsh spectra of a Boolean function at partial points and the Walsh spectra of its subfunctions, and on the binary Möbius transform, a novel algorithm is developed, which can theoretically construct all bent functions. Practically we enumerate all bent functions in 6 variables. With the restriction on the algebraic normal form, the algorithm is also efficient in more variables case. For example, enumeration of all homogeneous bent functions of degree 3 in 8 variables can be done in one minute with a P4 1.7 GHz computer; the nonexistence of homogeneous bent functions in 10 variables of degree 4 is computationally proved.     

On the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

Representations of Boolean functions by exclusive-OR sums (modulo 2) of pseudoproducts is studied. An ExOR-sum of pseudoproducts (ESPP) is the sum modulo 2 of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this form, and the length of a Boolean function in the class of ESPPs is defined as the minimum length of an ESPP representing this function. The Shannon function L ^ESPP(n) of the length of Boolean functions in the class of ESPPs is considered, which equals the maximum length of a Boolean function of n variables in this class. Lower and upper bounds for the Shannon function L ^ESPP(n) are found. The upper bound is proved by using an algorithm which can be applied to construct representations by ExOR-sums of pseudoproducts for particular Boolean functions.     

On Boolean functions with the sum of every two of them being bent

A set of Boolean functions is called a bent set if the sum of any two distinct members is a bent function. We show that any bent set yields a homogeneous system of linked symmetric designs with the same design parameters as those systems derived from Kerdock sets. Further we observe that there are bent sets of size equal to the square root of the Kerdock set size which consist of Boolean functions with arbitrary degrees.     

On second-order nonlinearity and maximum algebraic immunity of some bent functions in \mathcal{PS}^{+}

The rth-order nonlinearity and algebraic immunity of Boolean function play a central role against several known attacks on stream and block ciphers. Since its maximum equals the covering radius of the rth-order Reed-Muller code, it also plays an important role in coding theory. The computation of exact value or high lower bound on the rth-order nonlinearity of a Boolean function is very complected/challenging problem, especially when r>1. In this article, we identify a subclass of \({\mathcal{D}}_{0}\) type bent functions constructed by modifying well known Dillon functions having sharper bound on their second-order nonlinearity. We further, identify a subclass of bent functions in \({\mathcal {PS}}^{+}\) class with maximum possible algebraic immunity. The result is proved by using the well known conjecture proposed by Tu and Deng (Des. Codes Cryptogr. 60(1):1–14, 2011). To obtain rth-order nonlinearity (r>2), that is, whole nonlinearity profile of the constructed bent functions is still an open problem.     

Order of the length of Boolean functions in the class of exclusive-OR sums of pseudoproducts

An exclusive-OR sum of pseudoproducts (ESPP) is a modufo-2 sum of products of affine (linear) Boolean functions. The length of an ESPP is defined as the number of summands in this sum; the length of a Boolean function in the class of ESPPs is the minimum length of an ESPP representing this function. The Shannon length function L ^ESPP(n) on the set of Boolean functions in the class of ESPPs is considered; it is defined as the maximum length of a Boolean function of n variables in the class of ESPPs. It is proved that L ^ESPP(n) = ? (2 ⁿ /n ²). The quantity L ^ESPP(n) also equals the least number l such that any Boolean function of n variables can be represented as a modulo-2 sum of at most l multiaffine functions.     

Circulant discrete dynamical systems with threshold functions of at most three variables

We propose a method for finding sources of discrete dynamical systems of the circulant type with a q-valued arbitrary function at vertices. We find all sources, all fixed points, and some cycles, as well as lengths of some maximal chains outside cycles for the systems with Boolean threshold functions of at most three variables at the vertices.     

A conjecture about binary strings and its applications on constructing Boolean functions with optimal algebraic immunity

In this paper, a combinatorial conjecture about binary strings is proposed. Under the assumption that the proposed conjecture is correct, two classes of Boolean functions with optimal algebraic immunity can be obtained. The functions in first class are bent, and then it can be concluded that the algebraic immunity of bent functions can take all possible values except one. The functions in the second class are balanced, and they have optimal algebraic degree and the best nonlinearity up to now.     

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.     

On the coefficients of binary bent functions

We prove a 2-adic inequality for the coefficients of binary bent functions in their polynomial representations. The 2-adic inequality implies a family of identities satisfied by the coefficients. The identities also lead to the discovery of some new affine invariants of Boolean functions on .

     

MacWilliams duality and a Gleason-type theorem on self-dual bent functions

We prove that the MacWilliams duality holds for bent functions. It enables us to derive the concept of formally self-dual Boolean functions with respect to their near weight enumerators. By using this concept, we prove the Gleason-type theorem on self-dual bent functions. As an application, we provide the total number of (self-dual) bent functions in two and four variables obtaining from formally self-dual Boolean functions.     

Gowers $$U_3$$ norm of some classes of bent Boolean functions

The Gowers \(U_3\) norm of a Boolean function is a measure of its resistance to quadratic approximations. It is known that smaller the Gowers \(U_3\) norm for a Boolean function larger is its resistance to quadratic approximations. Here, we compute Gowers \(U_3\) norms for some classes of Maiorana–McFarland bent functions. In particular, we explicitly determine the value of the Gowers \(U_3\) norm of Maiorana–McFarland bent functions obtained by using APN permutations. We prove that this value is always smaller than the Gowers \(U_3\) norms of Maiorana–McFarland bent functions obtained by using differentially \(\delta \)-uniform permutations, for all \(\delta \ge 4\). We also compute the Gowers \(U_3\) norms for a class of cubic monomial functions, not necessarily bent, and show that for \(n=6\), these norm values are less than that of Maiorana–McFarland bent functions. 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.     

On the symmetric properties of APN functions

We study the symmetric properties of APN functions as well as the structure and properties of the range of an arbitrary APN function. We prove that there is no permutation of variables that preserves the values of an APN function. Upper bounds for the number of symmetric coordinate Boolean functions in an APN function and its coordinate functions invariant under a cyclic shift are obtained. For n ≤ 6, some upper bounds for the maximal number of identical values of an APN function are given and a lower bound is found for different values of an arbitrary APN function of n variables.     

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.     

Results on rotation symmetric bent functions

In this paper we analyze the combinatorial properties related to the Walsh spectra of rotation symmetric Boolean functions on even number of variables. These results are then applied in studying rotation symmetric bent functions. For the first time we could present an enumeration strategy for all the 10-variable rotation symmetric bent functions.     

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.