Abstract
Bent functions are Boolean functions in even number of variables that have maximal nonlinearity. They have flat Walsh–Hadamard spectrum and are of interest for their applications in algebra, coding theory and cryptography. A bent function is called self-dual if it coincides with its dual bent function. In current work we study the decomposition of the form \(\left( f_0,f_1,\ldots ,f_{2^k-1}\right) \) of the vector of values of a self-dual bent function, formed by the concatenation of \(2^k\) Boolean functions \(f_j\) in \(n-k\) variables. We treat the cases \(k=1,2\). Based on a spectral characterization, we introduce a notion of self-dual near-bent function in odd number of variables and prove that there exists a one-to-one correspondence between the notions of self-duality for even and odd number of variables. As a result the characterization for the decomposition \(\left( f_0,f_1\right) \) is obtained. For the decomposition \(f=\left( f_0,f_1,f_2,f_3\right) \) we prove that if sign vectors of subfunctions \(f_j\) are linearly dependent, then all these subfunctions are bent. We prove that for \({n\geqslant 6}\) the converse does not hold, that is the obtained condition is sufficient only. These results are also generalized for the case of an arbitrary bent function. Three new iterative constructions of self-dual bent functions are proposed. One of them allows to build a class of self-dual bent functions which cannot be decomposed into the concatenation of four bent functions. Based on the constructions a new iterative lower bound on the cardinality of the set of self-dual bent functions is obtained.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
Avoid common mistakes on your manuscript.
1 Introduction
Bent functions are Boolean functions in even number of variables that have maximal nonlinearity. They were studied in 60th of the previous century in the USA and USSR (see the report [12] and thesis [13] of Dillon, while the research in the Soviet Union was mentioned in historical sections of [24, 41]) and firstly published by Rothaus in [35]. They are mathematical objects of a great interest due to many applications in discrete mathematics, algebra, coding theory, cryptography. Having a property of maximal nonlinearity these functions can be used for obtaining Boolean and vectorial Boolean functions with good cryptographic properties. Another applications use the fact that bent functions and only them have flat Walsh–Hadamard spectrum that is crucial for some approaches within the signals theory, including CDMA technology. More information about them one can find in monographies [29, 41] and survey [7]. For extensive data about cryptographic properties of Boolean functions and other their applications one can refer to the books [6, 10]. Despite the long history of study there are many open problems related to bent functions, in particular, their cardinality is still unknown, their affine classification is completely studied only for small number of variables, obtaining of new constructions is also the goal worth pursuing.
For every bent function it is possible to define its dual Boolean function that defines the signs of its Walsh–Hadamard transform. This function is also bent and, in turn, its dual coincides with the initial function, so bent functions come in pairs. The duality mapping has a great interest in a scope of bent functions since it is the only known isometric mapping of the set of bent functions that is not an element of its group of automorphisms [5]. More information about the duals and the properties of the duality mapping one can find in [7].
Among different classes of bent functions the class of self-dual bent functions is emphasized. Essentially, self-dual are precisely such bent functions that coincide with their duals. They are also important from the perspective of obtaining polyphase sequences (sign vectors for Boolean case) with particular properties. Note that the polyphase sequence of self-dual bent function is the eigenvector of the Sylvester Hadamard matrix that appears in many areas of discrete mathematics and also in quantum computation. So the construction and characterization of self-dual bent functions has strong relation with the problem of description of eigenvectors of the Sylvester–Hadamard matrix, which is a long-standing problem of independent interest from linear algebra [15, 43]. Also self-dual bent functions are the fixed points of the duality mapping. Note that on self-dual bent functions and only on them the Rayleigh quotient of a Boolean function has maximal value for the case of even number of variables.
The notion of dual and anti-dual (precisely self-dual and anti-self-dual) bent functions in terms of sign vectors was initially considered by Preneel et al. [33], whereas more general definition of a self-dual bent function on a finite group was intriduced by Logachev, Sal’nikov and Yashchenko in [26]. The first deep study of self-dual Boolean bent function was made by Carlet et al. in paper [8], where several constructions and properties were obtained. From that time there appeared a number of papers devoted to the study and characterization of self-dual bent functions. In particular, the classification of quadratic self-dual bent functions was provided by Hou in [18]. The classification of qubic self-dual bent functions in 8 variables was done in paper [14], while the bounds for the cardinality of this class were deduced in [19]. A number of combinatorial and algebraic constructions one can find in [25, 27, 31, 34, 38]. Some combinatorial questions and open problems related to anti-self-dual bent functions were considered and solved in [39]. Metrical properties of self-dual bent functions were studied in papers [20,21,22,23]. Self-dual bent sequences, having connection with sign vectors of self-dual bent functions, were recently studied in [36, 37].
In current work we study the decompositions of vector of values of self-dual bent functions in n variables of the form \(\left( f_0,f_1,\ldots ,f_{2^k-1}\right) \), where \(f_j\) are Boolean functions in \(n-k\) variables. These functions are subfunctions obtained by fixing first k variables. We consider the cases \(k=1,2\). The properties of such subfunctions and some relations comprising them are treated. Note that the best known for today lower and upper bounds on the cardinality of the set of self-dual bent functions are based on the analysis of such decompositions. For details, these decompositions were considered in papers [8] (case \(k=1\)) from the perspective of generating all self-dual bent functions and [21] (case \(k=2\)) for the conditions when all \(f_j\) are bent.
The structure of the work is following. Necessary notation is given in Sect. 2. In Sect. 3 we introduce the concept of self-duality on near-bent functions in odd number of variables and prove that there is a one-to-one correspondence between self-dual bent function in n variables and near-bent functions in \(n-1\) variables having particular value of the Rayleigh quotient (Theorem 1). Note that this value coincides with the best known for today bound for the maximal value of the Rayleigh quotient for the case of odd number of variables. Further, in Sect. 4.2 we study the Gram matrix obtained via sign vectors of subfunctions obtained by fixing two variables of bent function. The general form of this matrix is deduced (Theorem 6). We use it for obtaining metrical relations between subfunctions of every bent function (Corollary 1). The Rayleigh quotients of subfunctions are characterized in Sect. 4.3 and their general form is obtained (Proposition 2). The form of the Gram matrix is explicitly used in Sect. 4.4, where we prove that given a self-dual bent function with linearly dependent sign vectors of subfunctions, all these functions are neccesarily bent (Theorem 3, Corollary 2). The converse of Theorem 3 is considered in Sect. 5. New constructions and a lower bound on the number of self-dual bent functions are presented in Sect. 6. In Sect. 7 we study the properties of the Gram matrix of decomposition for the general case, taking an arbitrary bent function. The Conclusion is in Sect. 8.
2 Notation
Let \(\mathbb {F}_2^n\) be a set of binary vectors of length n. For \(x,y\in \mathbb {F}_2^n\) denote \({\langle x,y\rangle =\bigoplus \limits _{i=1}^n{x_iy_i}}\), where sign \(\oplus \) denotes a sum modulo 2.
A Boolean function f in n variables is any map from \(\mathbb {F}_2^n\) to \(\mathbb {F}_2\). The set of Boolean functions in n variables is denoted by \(\mathcal {F}_n\). A sign vector (also known as polyphase vector or \(\{\pm 1\}\)-sequence) of \(f\in \mathcal {F}_n\) is an integer vector \({\left( (-1)^{f_0},(-1)^{f_1},\ldots ,(-1)^{f_{2^n-1}}\right) }\) of length \(2^n\), where \({\left( f_0,f_1,\ldots ,f_{2^n-1}\right) }\) is a vector of values (truth table) of the function f. Any Boolean function in n variables can be uniquely represented via the multivariate polynomial over \(\mathbb {F}_2\):
where \(a_z\in \mathbb {F}_2\) for all \(z\in \mathbb {F}_2^n\). Here we use the agreement \(0^0=1\). This representation is called the algebraic normal form (ANF) of the Boolean function f. The degree \(\textrm{deg}(f)\) of the function f is the maximal degree (number of terms) of the monimial from its algebraic normal form that has nonzero coefficient. If \(\textrm{deg}(f)\leqslant 1\), the function is called affine. If \(\textrm{deg}(f)=2\), the function is said to be quadratic.
The Hamming weight \(\textrm{wt}(x)\) of the vector \(x\in \mathbb {F}_2^n\) is the number of nonzero coordinates of x. The Hamming distance \(\textrm{dist}(f,g)\) between Boolean functions f, g in n variables is the cardinality of the set \({\left\{ x\in \mathbb {F}_2^n\vert f(x)\ne g(x)\right\} }\).
The Walsh–Hadamard transform of the function \(f\in \mathcal {F}_n\) is the integer function
For this functions the Parseval’s identity holds
A Boolean function f in an odd number m of variables is said to be near-bent if
For the case of an even number of variables, say n, the function f in n variables is said to be near-bent if
A Boolean function f in an even number n of variables is said to be bent if
The set of bent functions in n variables is denoted by \(\mathcal {B}_n\). The Boolean function \(\widetilde{f}\in \mathcal {F}_n\) such that \(W_f(y)=(-1)^{\widetilde{f}(y)}2^{n/2}\) for any \(y\in \mathbb {F}_2^n\) is said to be dual of f. Note that the dual function is uniquely defined for every bent function, moreover the function \(\widetilde{f}\) is bent as well. A bent function f is said to be self-dual if \(f=\widetilde{f}\), and anti-self-dual if \(f=\widetilde{f}\oplus 1\). The set of self-dual bent functions in n variables is denoted by \(\mathcal{S}\mathcal{B}_n^+\).
The Rayleigh quotient of a Boolean function in n variables is a number
This spectral characteristics of a Boolean function in a scope of bent functions were studied in [11]. It is interesting for bent functions since it completely characterizes the Hamming distance between the function and its dual. Indeed, for any bent function f it holds
For a Boolean function f in n variables we call the number
the sub-normalized Rayleigh quotient.
Let \(I_n\) be the identity matrix of size n and \(H_n=H_1^{\otimes n}\) be the n-fold tensor product of the matrix \(H_1\) with itself, where
This matrix is known as the Sylvester–Hadamard matrix. It is known the Hadamard property of this matrix
where \(H_n^{\text {T}}\) is transpose of \(H_n\) (it holds \(H_n^{\text {T}}=H_n\) by symmetricity of \(H_n\)). Denote by \(\mathcal {H}_n=2^{-n/2}H_n\) its normalized version.
The matrix \(H_n\) describes the Walsh–Hadamard transform in matrix form. More precisely, it is known that the rows (columns) of this matrix are sign vectors of all linear Boolean functions in n variables \(\langle a,x\rangle \), \(a\in \mathbb {F}_2^n\), given in lexicographical order of vectors a, see [10]. Then the Walsh–Hadamard transform at the point \(y\in \mathbb {F}_2^n\) is just the inner product of sign vector of the linear function \(\langle y,x\rangle \), \(x\in \mathbb {F}_2^n\), and sign vector F of the function f. Thus, the vector whose coordinates are Walsh–Hadamard coefficients is simply \(H_nF\). So in terms of sign vectors the Rayleigh quotient of the function f has the expression
where F is its sign vector.
For a real \(d\times d\) matrix A a nonzero vector \(v\in \mathbb {R}^d\) is called an eigenvector of A if \(Av=\lambda v\) for some \(\lambda \in \mathbb {C}\). This number is called the eigenvalue of A, associated with v.
It is clear that sign vectors if self-dual bent functions are eigenvectors of the normalized Sylvester–Hadamard matrix that correspond to the eigenvalue 1. At the same time sign vectors of anti-self-dual bent functions are eigenvectors of the normalized Sylvester–Hadamard matrix that correspond to the eigenvalue \((-1)\).
3 Decomposition of the form \(\left( f_0,f_1\right) \)
In this section we study the decomposition for the case \(k=1\), that is consider the subfunctions of self-dual bent functions that are obtained by fixing the first variable. It is known that for any bent function in n variables such subfunctions are near-bent functions in \(n-1\) variables with disjoint Walsh–Hadamard spectrum (see [42], for example).
In [8] and [14] the subfunctions in \(n-1\) variables were used in the algorithms for the enumeration of all self-dual bent functions of prescribed algebraic degree. These algorithms explicitly exploit the fact that the vector (Y, Z), where \({Y,Z\in \left\{ \pm 1\right\} ^{2^{n-1}}}\), is the sign vector of some self-dual bent function in n variables if and only if
Regarding spectral characterization it is known [8] that for any Boolean function, say f, in even number n of variables it holds
with equality if and only if f is either self-dual \(\left( +2^{3n/2}\right) \) or anti-self-dual \(\left( -2^{3n/2}\right) \) bent. It follows that extremal values are achieved if and only if
or
Accordingly, only self-dual and anti-self-dual bent functions possess these conditions for the case of an even number of variables.
3.1 Self-duality for near-bent functions
Let \(m\geqslant 3\) be an odd integer. In current paper we introduce the notions of self-duality and anti-self-duality for near-bent functions in odd number of variables that are based on the spectral characterization. We are to call a near-bent function g in m variables self-dual if
In order, g is called an anti-self-dual near-bent if
Finding the exact maximal (minimal) value of the Rayleigh quotient of a Boolean function in an odd number m of variables is an open problem. It is caused by the fact that for odd m there are no eigenvectors of the Sylvester Hadamard matrix \(H_m\), with coordinates having the same absolute value. It is known that, as was shown in [8], it holds
For this bound the authors used the concatenation of two self-dual bent functions in \({m-1}\) variables, so the obtained value was called the bent-concatenation bound. Nevertheless the experiments have shown that this bound is not tight, at least for small values of m.
Self-dual near-bent functions, proposed in current paper, are extremal objects within the set of near-bent functions in odd number of variables in a spectral sense, as we show in the following statement
Proposition 1
Let g be a near-bent function in m variables, then
with equality if and only if f is either self-dual or anti-self-dual near-bent.
Proof
By definition of the Rayleigh quotient we have
The multiplicities of Walsh coefficients of any near-bent function in m variables are well known (see [30], for example), we list them in Table 1.
Consider two nonnegative integers \(a_1,a_2\), describing the signs of nonzero terms in the sum (2):
Then we have a following system
It is clear that the maximal value of \(S_g\) corresponds to the case \({a_2=0}\). Then \({a_1=2^{m-1}}\) and
By the same arguments the minimal value of \(S_g\) corresponds to the case \({a_1=0}\), that is \({a_2=2^{m-1}}\), and
Thus, it holds \({|S_g|\leqslant 2^{(3m-1)/2}}\) with the equality only when either
or
that is g is either self-dual or anti-self-dual near-bent. \(\square \)
Thus, the value of the Rayleigh quotient of a self-dual near-bent function coincides with the bound for its maximal value, which is the best known one for today. Moreover, on self-dual near-bent functions and only on them the value of the Rayleigh quoutient is maximal within the set of near-bent functions. Just the same holds for the minimal value and anti-self-dual near-bent functions.
3.2 Connection between self-duality for even and odd cases
Further we show that there exists a bijection between two types of self-duality with a descent step from even to odd number of variables.
Theorem 1
There exists a one-to-one correspondence between the set of self-dual bent functions in \(n\geqslant 4\) variables and the set of (anti-)self-dual near-bent functions in \({n-1}\) variables.
Proof
Put \(\mathcal {H}=\mathcal {H}_{n-1}\). Let f be a self-dual bent functions in n variables and \({\left( f_0,f_1\right) }\) be its truth table, where \(f_i\in \mathcal {F}_{n-1}\), \(i=1,2\). Denote by \(F_i\) the sign vector of \(f_i\), \({i=1,2}\). Then it holds
that is equal to the system
Firstly one can notice that
therefore it holds \(\left\langle F_0,F_1\right\rangle =0\) (It also follows from the orthogonality of \(\mathcal {H}F_0\) and \(\mathcal {H}F_1\) and symmetricity of \(\mathcal {H}\)). Now consider the first equation from the system above:
Since \(\mathcal {H}^2=I_{n-1}\), it is the same as
Consider the inner product
The orthogonality of \(F_0\) and \(F_1\) implies the condition
Under the used notation we have
Since from (1) it immediately follows that function \(f_1\) can be characterized by \(f_0\), there exists an injective mapping from the set of all self-dual bent functions in n variables to the set of self-dual near-bent functions in \({n-1}\) variables. This mapping essentially maps every self-dual bent function to its subfunction obtained by fixing the first coordinate with 0.
Now let \(f_0\) be a self-dual near-bent function in \(n-1\) variables. From Proposition 1 it follows that the value of \((-1)^{f_0(y)}\) and the sign of the Walsh–Hadamard coefficient \(W_{f_0}(y)\) of \(f_0\) are agreed in a sense that their product is nonnegative for every \({y\in \mathbb {F}_2^{n-1}}\). Let \(F_0\) be a sign vector of \(f_0\). Define
From (1) it follows that if \(F_1\in \left\{ \pm 1\right\} ^{2^{n-1}}\), then the vector \({\left( F_0,F_1\right) }\) is the sign vector of a self-dual bent function in n variables. Indeed, the relation (1) for \({\left( F_0,F_1\right) }\) is
and its multiplication by \(\left( I_{2^{n-1}}-\frac{2H_{n-1}}{2^{n/2}}\right) \) from the left yields (4) since
It is clear that the fact that \(W_{f_{0}}(y)\) and \((-1)^{f_0(y)}\) are being agreed implies that
then we can define a Boolean function in \({n-1}\) variables, say \(f_1\), which has a sign vector \(F_1\) and consider the relation (4) in componentwise form
So the vector \({\left( F_0,F_1\right) }\) is the sign vector of a self-dual bent function in n variables. Note that this self-dual bent function is unique since the pair of subfunctions of any self-dual bent function is defined uniquely.
Thus, it follows that for any self-dual near-bent Boolean function in \(n-1\) variables there exists a self-dual bent function in n variables, moreover this function is an unique one.
Finally, we have that the mapping that maps every self-dual bent function to its subfunction obtained by fixing the first coordinate with 0, is an injective and surjective one from the set of all self-dual bent functions in n variables to the set of self-dual near-bent functions in \({n-1}\) variables. Therefore there exists a bijection between these sets of Boolean functions.
By the same arguments one can show that there exists a one-to-one correspondence between the set of all self-dual bent functions in \(n\geqslant 4\) variables and the set of anti-self-dual near-bent functions in \({n-1}\) variables. In more details, it can be done by considering the second equation from (3) and showing that
So it follows that subfunction \(f_1\) is anti-self-dual near-bent function in \(n-1\) variables.
Again, from (1) it immediately follows that function \(f_0\) can be characterized by \(f_1\), hence there exists an injective mapping from the set of all self-dual bent functions in n variables to the set of anti-self-dual near-bent functions in \({n-1}\) variables. It maps every self-dual bent function to its subfunction obtained by fixing the first coordinate with 1.
Given an anti-self-dual near-bent function \(f_1\) in \(n-1\) variables with sign vector \(F_1\), for surjectivity of the mentioned mapping it is enough to consider the vector
From Proposition 1 it follows that the value of \((-1)^{f_1(y)}\) and the sign of the Walsh–Hadamard coefficient \(W_{f_1}(y)\) of \(f_1\) are disagreed in a sense that their product is nonpositive for every \({y\in \mathbb {F}_2^{n-1}}\). Therefore the vector \({\left( F_0,F_1\right) }\) consists of \(\pm 1\) only, that is it is the sign vector of a self-dual bent function in n variables. This self-dual bent function is unique since the pair of subfunctions of any self-dual bent function is defined uniquely.
Thus, it follows that for any anti-self-dual near-bent Boolean function in \(n-1\) variables there exists a self-dual bent function in n variables, moreover this function is an unique one. \(\square \)
We have shown that for self-dual bent function f with vector of values \(\big (f_0,f_1\big )\) the subfunction \(f_0\) is always self-dual near-bent and \(f_1\) is always anti-self-dual near-bent. From the other side for every self-dual near-bent function g in \(n-1\) variables there exists a unique self-dual bent function in n variables such that g is its subfunctions obtained by fixing the first variable with 0. At the same time for every every anti-self-dual near-bent function h in \(n-1\) variables there also exists a unique self-dual bent function in n variables such that h is its subfunctions obtained by fixing the first variable with 1.
Thus, the mentioned bijection is defined via the mapping \(f\leftrightarrow f_0\) for self-dual near-bent case and \(f\leftrightarrow f_1\) for anti-self-dual near-bent one.
We also have a bijection between self-dual and anti-self-dual near-bent functions, it is provided by the considerations above and the relation (1).
There is an interesting consequence that if we want to obtain Boolean function in even number n of variables that has the maximal value of the Rayleigh quotient, by using the concatenation of two Boolean functions in \({n-1}\) variables, we likely should not take functions that have extremal values of the Rayleigh quotient. The same holds if we are to construct a Boolean function in odd number m of variables that also has the maximal value of the Rayleigh quotient. Since in the first case self-dual or anti-self-dual near-bent functions are not chosen, therefore the obtained Boolean functions will not be self-dual bent. In the second case we obtain a bent-concatenation bound that is likely to be not tight for infinitely many n.
The reason of that can be explained by the following considerations. Assume we have the Boolean function f in k variables (even or odd) with sign vector F, which is a concatenation of functions \(f_0\) and \(f_1\) in \({k-1}\) variables with sign vectors \(F_0\) and \(F_1\). Then it holds
where we have different signs for the Rayleigh quotients of the subfunctions and also the term comprising both subfunctions, one of which is given in its Walsh–Hadamard transfrom form.
Thus, the maximization of the Rayleigh quotient of subfunctions may lead to the “instability” and decrease of the Rayleigh quotient of the whole function. The maximization of the Rayleigh quotient for the case of an odd number of variables is a problem of a complex optimization, in particular, of the values of the Rayleigh quotient of its subfunctions.
4 Decomposition of the form \(\left( f_0,f_1,f_2,f_3\right) \) for self-dual case
In this section we study the subfunctions of self-dual bent functions that are obtained by fixing the first and the second coordinates of the argument. Metrical properties of subfunctions and interconnections between them are considered.
Subfunctions of a bent function, in more general form, comprising the restriction of a bent function on all subspaces of codimension 2, were extensively studied in works [3, 4]. The considered sets of subfunctions were referred to as 4-decompositions of a bent function. In particular, it was shown that such subfunctions of a bent function in n variables have the same Walsh–Hadamard spectrum: either all of them are bent, all are the three valued almost optimal (these are precisely near-bent functions with the spectrum having three values 0, \(\pm 2^{n/2}\)), or they have the same Walsh–Hadamard spectrum with five values 0, \({\pm 2^{(n-2)/2}}\), \(\pm 2^{n/2}\). In [17] the family of so-called totally (non-overlap) disjoint spectra plateaued functions was studied. These functions are interesting since they are constituent functions in the 4-decompositions.
Throughout this section given a function f in n variables we will refer to four Boolean functions \(f_i\), \({i=0,1,2,3}\), in \(n-2\) variables as to its subfunctions obtained by fixing the first and the second coordinates of the argument with the values \(\{(00),(01),(10),(11)\}\), correspondingly. In turn, vector of values of f will have the form \({\left( f_0,f_1,f_2,f_3\right) }\). The sign vector of \(f_i\) will be denoted by \(F_i\), \({i=0,1,2,3}\). Let the notation \(\mathcal {H}\) states for \(\mathcal {H}_{n-2}\).
Further we will use the following observation. Let f be a bent function in n variables, then
or, equivalently,
where \(R_i\), \(i=0,1,2,3\), are sign vectors of subfunctions of \(\widetilde{f}\). Obviously, the function f is self-dual if and only if \(R_i=F_i\), \(i=0,1,2,3\).
4.1 Concatenation of four bent functions
The case when all four subfunctions are bent essentially leads to the idea of an iterative construction of a bent function in \({n+2}\) variables through four bent functions in n variables. In [33] Preneel et al. proved that given four bent functions \(f_i\), \({i=0,1,2,3}\), in n variables, the concatenation of vectors of values of \(f_i\) yields a bent function in \(n+2\) variables if and only if
In terms of duals this condition is equivalent to the following
Note that the idea of concatenation also appears in a scope of so-called “bent based” bent sequences, see [1]. The approach allows to obtain a bent sequence of length 4l through the concatenation of four bent sequences of length l provided the similar conditions on these sequences are satisfied.
Bent functions in \(n+2\) variables obtained by the concatenation of four bent functions in n variables were also studied in [40] from the point of view of obtaining lower bounds on the cardinality of the set of bent functions. Such functions were referred to as bent iterative functions. Concatenation construction was also considered in [16] in a scope of generic concatenation methods. New constructions of bent functions, based on the concatenation, were recently proposed in [2, 32]. In [9] one can find another iterative approaches.
There are known two constructions of self-dual bent functions in \(n+2\) variables, based on the concatenation of four bent functions in n variables. They are
-
the construction C1:
$$\begin{aligned} \big (f,\widetilde{f},\widetilde{f},f\oplus 1\big ), \end{aligned}$$where f is a bent function in n variables [8];
-
the construction C2:
$$\begin{aligned} \left( f,g\oplus 1,g,f\right) , \end{aligned}$$where f is a self-dual bent function, g is an anti-self-dual bent function both in n variables [21].
It is worth noting that the best known for today lower bound on the cardinality of the set of self-dual bent functions is the sum of cardinalities of C1 and C2.
In [21] the criteria of self-duality of a bent function in \(n+2\) variables obtained via concatenation of four bent functions in n variables was presented.
4.2 Gram matrix for sign vectors of subfunctions
In this subsection we will study the Gram matrix of vectors \(F_i\), \({i=0,1,2,3}\) which are sign vectors of subfunctions of a Boolean function f. Recall that elements \(g_{ij}\) of the Gram matrix of vectors \({\left\{ v_k\right\} _{k\in M}\subset \mathbb {R}^d}\) are inner products between \(v_i\) and \(v_j\), \({i,j\in M}\). The determinant of the Gram matrix is called the Gramian of the corresponding system of vectors. The basic properties of real Gram matrices are:
-
symmetricity;
-
positive semi-definiteness;
-
the Gramian is zero if and only if the vectors are linearly dependent.
Denote the inner products by \({g_{ij}=\left\langle F_i,F_j\right\rangle }\), \({i,j=0,1,2,3}\).
The form of the Gram matrix of self-dual bent functions is characterized in the following statement
Theorem 2
The Gram matrix of any self-dual bent function in n variables has form
for some even integers a, b such that
Proof
For self-dual case the system (5) has form
Consider pairwise inner products of right parts of all equations in the system (6). The symmetricity of \(\textrm{Gram}(f)\) implies that we have at most six different coefficients outside the main diagonal in fact. For example, the 1st equation’s expression inner product with itself is
It yields the following equation on the coefficients:
Finally, after considering the rest ones, we have the following system of equations that describe necessary relations between the entries of the Gram matrix:
The system has rank 4, its general solution is
for \(g_{12}\) and \(g_{23}\) being free variables. Denote \(b=-g_{23}\) and \(a=g_{12}\), then we obtain the desired form of the Gram matrix:
Now we are to point essential bounds on values of a and b and deduce some relations between them. In order to do it recall that any Gram matrix is positive semi-definite, hence all its eigenvalues must be nonnegative. The matrix \(\textrm{Gram}(f)\) has four eigenvalues, they are
Note that the eigenvalue \(2^{n-2}-a\) has algebraic multiplicity 2, also its nonnegativity is obvious. The rest imply that
that is
and, consequently,
where \(|b|\) is essentially bounded by \(2^{n-2}\) from above. \(\square \)
For example, the constructions C1 and C2 provide the following matrices:
which has rank 1 in the case when \(\mathcal {S}_{f}=2^{n-2}\) that is f is self-dual bent, and 2 otherwise, and
with rank equal to 2. It is obvious that for both constructions the sets \(\left\{ F_i\right\} \) are linearly dependent.
Inner products between sign functions are interesting since it is easy to deduce the Hamming distance between two Boolean functions provided the inner product between their sign functions is known. Indeed,
Thus, Theorem 6 can be reformulated in terms of Hamming distances between subfunctions:
Corollary 1
Let f be a self-dual bent function in n variables. The Hamming distances between \(\left\{ f_i\right\} _{i=0}^3\) are characterized by the matrix
for some positive even integers \(d_1,d_2\) such that
Proof
The relation between the inner product and the Hamming distance yields the matrix whereas the inequality
is obtained from
with
\(\square \)
4.3 Rayleigh quotients of subfunctions
Another application of the Gram matrix deals with the relations between Rayleigh quotients of subfunctions. Let f be a self-dual bent function in n variables. Recall that by (5) we have
The Gram matrix provides the expression of the Rayleigh quotients of the subfunctions in terms of the coefficients a ans b.
Finally we have expressions
and
It follows that the Rayleigh quotients of \(f_0\) and \(f_3\) coincide, as well as of \(f_1\) and \(f_2\). The sum of all Rayleigh quotients is equal to
We collect all this to the following statement
Proposition 2
Let f be a self-dual bent function in n variables with Gram matrix
then
4.4 Sufficient condition for the subfunctions of self-dual bent function to be bent
In this subsection we study the special cases of parameters a, b for which the Gram matrix is singular.
Recall that the Gramian is equal to the product of the eigenvalues of the matrix so for a self-dual bent function f with the Gram matrix \(\textrm{Gram}(f)\) it has the following expression
Further the values such that the Gramian is zero will be considered for a self-dual case.
But before, we can characterize all self-dual bent functions that possess \({a=2^{n-2}}\), that is \({f_1=f_2}\). In order to do it consider the general system
which is transformed to
By the triangle inequality we obtain
From the other side by orthogonality of the matrix \(\mathcal {H}\) we obtain that \({\left\Vert 2\mathcal {H}F_1 \right\Vert =2\cdot 2^{(n-2)/2}=2^{n/2}}\). So we have an equality
hence \(F_0\) and \(F_3\) are linearly dependent vectors, that is either \({F_0=F_3}\) or \({F_0=-F_3}\). But from the second and third equalities it follows that \(F_0\) and \(F_3\) can not coincide, therefore \({F_3=-F_0}\). Finally we obtain \(F_0=\mathcal {H}F_1\), that is all subfunctions are bent and \(f_0\) and \(f_1\) are dual of each other. This situation is exactly the construction C1.
Proposition 3
If for a self-dual bent function f it holds \(f_1=f_2\), then it is constructed via C1.
In Sect. 4.2 it was mentioned that sign vectors of subfunctions mentioned in constructions C1 and C2 are linearly dependent. Also all those subfunctions are bent. The next results covers all combinations for which the Gramian is zero.
Theorem 3
If the Gram matrix of a self-dual bent function f is singular then subfunctions \(\{f_i\}_{i=0}^3\) are bent.
Proof
At first notice that the condition (1) for the case of subfunctions in \(n-2\) variables has the following form
Also by the condition \(\mathcal {H}^2=I_{2^{n-2}}\) we obtain
Both of conditions (8) and (9) allow to characterize all possible combinations of signs of \(F_i\) and \(\mathcal {H}F_i\), \(i=0,1,2,3\). As it was mentioned in Sect. 4.1, either all of subfunctions are bent, all are near-bent, or they have the same Walsh–Hadamard spectrum with five values 0, \(\pm 2^{(n-2)/2}\), \(2^{n/2}\) [3, 4]. It means that in general case \({\mathcal {H}F_i\in \{0,\pm 1,\pm 2\}}\), \({i=0,1,2,3}\).
For every row of Table 2 by \(c_i\) we denote the number of vectors \({y\in \mathbb {F}_2^{n-2}}\) for which the corresponding sequence of values and signs stands. The Gram matrix from Theorem 6 for the function f gives six equations:
Finally, taking into account the cardinality of the space \(\mathbb {F}_2^{n-2}\), we obtain the system of 7 linear equations
The system has rank 7, its equations in a row echelon form yield the relations
Now we are to consider all combinations of a, b such that the Gramian (7) is zero. In order to do it we take \(c_i\), \({i=1,2,\ldots ,16}\), as nonnegative integer variables. Before one can note that one of subfunctions is bent (consequently all of them are bent) if and only if \(c_i=0\) for \({i=1,2,\ldots ,8}\). So we introduce an auxiliary equation
where k is nonnegative integer and put it to the system. The rank of the resulting system of equations is 8. From the nonnegativity of variables it follows that if for a fixed pair a, b provided by some self-dual bent function, the system has no solutions with positive k, all subfunctions of this function are bent.
At first, note that for every eigenvalue of the Gram matrix given in the general form there exists a self-dual bent function with a, b such that the eigenvalue is zero. Indeed, for \({\lambda _{1,2}=2^{n-2}-a=0}\) the construction C1 is suitable, since it provides \(a=2^{n-2}\), \(b=\mathcal {S}_f\). For \({\lambda _{3}=2^{n-2}+a-2b=0}\) and \({\lambda _{4}=2^{n-2}+a+2b=0}\) the contruction C2 meets the desired condition because it is clear that it admits \({a=-2^{n-2}}\), \({b=0}\).
Now consider all pairs of a, b, vanising the corresponding eigenvalue, and analyze the obtained system:
-
\(2^{n-2}-a=0\): in this case
$$\begin{aligned} c_1=c_2=c_3=c_4=c_5=c_6=c_7=c_8=0, \end{aligned}$$that holds if only if \(k=0\).
-
\(2^{n-2}+a-2b=0\): the relations between variables must satisfy
$$\begin{aligned} c_1+c_4&=\frac{k}{4},&c_2+c_3&=\frac{k}{4},&c_5+c_6&=\frac{k}{4},&c_7+c_8&=\frac{k}{4},&c_{10}+c_{11}&=-\frac{k}{4}, \end{aligned}$$so the solution does not exist if \(k>0\), therefore \(k=0\).
-
\(2^{n-2}+a+2b=0\): we have relations
$$\begin{aligned} c_1+c_4&=\frac{k}{4},&c_2+c_3&=\frac{k}{4},&c_5+c_6&=\frac{k}{4},&c_7+c_8&=\frac{k}{4},&c_{13}+c_{16}&=-\frac{k}{4}, \end{aligned}$$so again the solution does not exist if \({k>0}\), therefore \({k=0}\).
\(\square \)
From Theorem 3 and properties of the Gram matrix we conclude that
Corollary 2
If sign vectors of subfunctions of a self-dual bent function f are linearly dependent then subfunctions \(\{f_i\}_{i=0}^3\) are bent.
Thus, we obtain a sufficient condition for bentness of the subfunctions. The interesting question arises: is it necessary to have linear dependence for sign vectors of subfunctions in order to obtain a self-dual bent function with bent subfunctions? In particular, the experiments show that
Remark 1
For \(n=4\) all self-dual bent functions with bent subfunctions have singular Gram matrices.
We consider this question further in Sect. 5. Note that according to experiments conducted for small n, most of self-dual bent functions are not bent concatenations hence their Gram matrices are necessarily non-singular. In particular, from 42896 self-dual bent functions in 6 variables only 3408 are bent concatenations and 192 of them have singular Gram matrices.
From Table 2 we can also deduce an interesting property that can be useful.
Proposition 4
Let f be an (anti-)self-dual bent function in n variables, then \(\left\{ f_i\right\} _{i=0}^3\) are bent if and only if
This condition is not well seen from the results of [21] but can be deduced from [3]. Anti-self-dual case follows from the existence of a certain bijection between self-dual and anti-self-dual bent functions (see [8, 18, 22]). By using the condition we can clarify the decomposition of a self-dual bent function with bent subfunctions:
From Corollary 1 it follows that Hamming weights of functions \({f_0\oplus f_1}\) and \({f_0\oplus f_2}\) coincide.
5 Linear independence of sign vectors and bentness of the subfunctions of self-dual bent function
As it was mentioned in the previous section, the singularity of the Gram matrix is also necessary for the case \({n=4}\). It is known that all (self-dual) bent functions in 4 variables are quadratic. So further we are to check if this property holds for any quadratic self-dual bent function.
Any quadratic function in n variables, say f, can be written as
where A is an upper triangular matrix of order \(n\times n\) over \(\mathbb {F}_2\) and d is constant. The quadratic part of f, as well as its Hamming weight, is completely characterized by the so-called associate alternating matrix \({Q=A\oplus A^{\textrm{T}}}\), see MacWilliams and Sloane [28]. Recall that a square matrix over \(\mathbb {F}_2\) is called alternating if it is symmetric with zero diagonal.
In [18] self-dual quadratic bent functions were completely characterized through a classification of all \(n\times n\) involutory alternating matrices over \(\mathbb {F}_2\) under the action of the orthogonal group. In particular, it was proved that the function (10) is self-dual or anti-self-dual bent if and only if \(Q^2=I_n\), that is Q is an involution (initially was proved in [8]), and the matrix \({QAQ\oplus A^\textrm{T}}\) is an alternating matrix. We will use this result in following.
Denote \(m=n-2\) and consider arbitrary (anti-)self-dual quadratic bent function in n variables:
where \(\lambda _1,\lambda _2,\lambda _{12}\in \mathbb {F}_2\), \(u,v\in \mathbb {F}_2^{m}\) and g is a function in m variables with degree at most 2. Without loss of generality we assume that \(d=0\). The subfunctions \(\{f_i\}_{i=0}^3\) have form
Assume these subfunctions are bent, then g is bent and by Proposition 4 we have \({\lambda _{12}=1}\). It is clear that f has invertible Gram matrix if and only if the vectors u, v are linearly independent.
The upper triangular matrix A and associate alternating matrix Q are
where the \(m\times m\) submatrix \(B=\big (b_{ij}\big )\) characterizes quadratic function g. Note that the matrix \(B\oplus B^{\textrm{T}}\) must have full rank since g is bent. Associate alternating matrix Q must be an involutory matrix, therefore we have
where \(M=\left( m_{ij}\right) \) is a square matrix with elements \({m_{ij}=u_iu_j\oplus v_iv_j}\), \({i,j=1,2,\ldots ,m}\). The relation \(Q^2=I_n\) holds if and only if
Also, one can easily show that \(M^2\) is all-zero matrix, hence \(\left( B\oplus B^{\textrm{T}}\right) ^4=I_{m}\).
The next condition for (anti-)self-duality of quadratic bent functions is that the matrix \({QAQ\oplus A^{\textrm{T}}}\) is alternating. In [18] it was noted that under condition \(Q^2=I_n\) the matrix \({QAQ\oplus A^{\textrm{T}}}\) is symmetric, hence it is alternating if and only if its diagonal elements are equal to zero. Consider them in details:
where \(c_i=\big (B\oplus B^{\textrm{T}}\big )_iB\big (B\oplus B^{\textrm{T}}\big )^{(i)}\), \(i=1,2,\ldots ,m\).
Let us gather all the conditions for (anti-)self-duality of quadratic bent function, given in the form of decomposition with a respect to the first and the second variables:
These relations form the criteria of (anti-)self-duality of a bent function and we implicitly join here the requirement that the matrix \(B\oplus B^{\textrm{T}}\) has full rank and also take into account linear independence of u and v.
We are to provide the construction that satisfies criteria (\(\star \)). Let the matrix B and vectors u, v be equal to
for some \(b_{11},b_{22},\ldots ,b_{mm}\in \mathbb {F}_2\). These numbers must satisfy the following consistent system of m linear equations:
which has rank m/2 or \(m/2+1\), depending the parity of m. So any solution yields either self-dual or anti-self-dual quadratic bent function with bent subfunctions and nonzero Gramian.
If we obtain an anti-self-dual bent function, say f, then just apply the following transformation:
that maps it to the self-dual quadratic bent function g. It follows from the fact that the affine mapping
is a bijection between the sets of self-dual and anti-self-dual bent functions, see [8, 18, 22]. However the function g has Gram matrix
for which it holds \(\textrm{Gramian}(g)=\textrm{Gramian}(f)\).
For now we can give an answer to the question about necessity of singularity of the Gram matrix for the subfunctions to be bent that is to resolve the converse of Theorem 3.
Theorem 4
For every even \(n\geqslant 6\) there exists a (quadratic) self-dual bent function f in n variables with invertible Gram matrix, such that subfunctions \(\{f_i\}_{i=0}^3\) are bent.
One can show that this assertion holds also for anti-self-dual bent functions. For proof it is enough to consider aforementioned one-to-one correspondence between the sets of self-dual and anti-self-dual bent functions.
From Theorem 4 and properties of the Gram matrix we again conclude that
Corollary 3
For every even \(n\geqslant 6\) there exists a self-dual bent function f in n variables whose subfunctions \(\{f_i\}_{i=0}^3\) are bent functions with linearly independent sign vectors.
Thus, the converse of Theorem 3 does not hold for \(n\geqslant 6\), that is the linear dependence of sign vectors provides only sufficient condition for subfunctions in \({n-2}\) variables to be bent. It is also clear why this does not hold for \(n=4\) since there are only two distinct vectors in \(\mathbb {F}_2^2\) that could satisfy the criteria (⋆): (00) and (11), but these vectors are linearly dependent.
6 New iterative constructions and lower bound for the cardinality of the set of self-dual bent functions
In current section we propose three new constructions C3, C4 and C5 of self-dual bent functions. The constructions use a 4-variables step. Let h be a bent function in \({n-4}\) variables, r be a self-dual bent function in \({n-4}\) variables and g be an anti-self-dual bent function in \({n-4}\) variables.
-
the construction C3:
$$\begin{aligned} \big (h,g,g\oplus 1,h,\widetilde{h},r,r\oplus 1,\widetilde{h}, \widetilde{h},r\oplus 1,r,\widetilde{h},h\oplus 1,g,g\oplus 1,h\oplus 1\big ) \end{aligned}$$It is clear that the subfunctions \(f_0,f_1,f_2,f_3\) are bent;
-
the construction C4:
$$\begin{aligned} \big (h,g,\widetilde{h},r,g\oplus 1,h,r\oplus 1,\widetilde{h}, \widetilde{h},r\oplus 1,h\oplus 1,g,r,\widetilde{h},g\oplus 1,h\oplus 1\big ) \end{aligned}$$The subfunctions \(f_0,f_1,f_2,f_3\) are bent if and only if \({h\oplus \widetilde{h}\oplus r\oplus g=0}\), so in some cases we do not obtain bent decompositions. Thus, this construction also yields a class of bent functions which cannot be decomposed into the concatenation of four bent functions;
-
the construction C5:
$$\begin{aligned} \big (h,h\oplus 1,\widetilde{h},\widetilde{h},h,h,\widetilde{h}\oplus 1, \widetilde{h},\widetilde{h},\widetilde{h},h\oplus 1,h,\widetilde{h}\oplus 1,\widetilde{h},h\oplus 1,h\oplus 1\big ) \end{aligned}$$It is clear that the subfunctions \(f_0,f_1,f_2,f_3\) are bent.
It is possible to estimate the C4 case related with the (im)possibility of a bent decomposition:
Proposition 5
The number of self-dual bent functions in \(n\geqslant 8\) variables constructed via C4, which cannot be (can be) decomposed into the concatenation of four bent functions, is at least \(2\big |\mathcal{S}\mathcal{B}^+_{n-6}\big |^2\).
Proof
Let \(r_1\) and \(r_2\) be two bent functions in \({n-6}\) variables \({x_7,x_8,\ldots ,x_n}\), such that the first one is either self-dual or anti-self-dual while the second is a self-dual one. Define
one can check that
Thus, the self-dual bent function constructed via C4, is the concatenation of four bent functions.
Finally, note that in order to obtain the function which is not the concatenation of four bent functions, it is enough to take a negation of the two-variables part of either f or g, for instance
\(\square \)
The constructions C3, C4 and C5 have the following Gram matrices:
with parameters \({a=0}\), \({b=2\mathcal {S}_{h}}\), \({a=b=0}\) and \({a=4\mathcal {S}_{h},b=0}\), correspondingly. The Gramian of C3 is equal to \({2^{4n-8}-2^{2n}\mathcal {S}_{h}^2}\) hence it is nonzero besides the case \(|\mathcal {S}_{h}|=2^{n-4}\), that is when h is either self-dual or anti-self-dual bent. The Gramian of C4 is equal to \(2^{4n-8}\). The Gramian of C5 is equal to \({\left( 2^{2n-4}-16\mathcal {S}_{h}^2\right) ^2}\), hence it is nonzero besides the case \(|\mathcal {S}_{h}|=2^{n-4}\), that is again when h is either self-dual or anti-self-dual bent.
Note that the constructions C1, C2, C3 and C4 provide disjoint sets of self-dual bent functions whereas C5 has clear intersection with C1 and C2. So we conclude that the sum of the cardinalities of the first four constructions and the disjoint part of C5 is a lower bound for the cardinality of the set of self-dual bent functions in n variables.
Theorem 5
The number of self-dual bent functions in \(n\geqslant 6\) variables is at least
Thus, it increases the previous iterative bound \({\left|{{\textbf {C}}\varvec{1}}\right|+\left|{{\textbf {C}}\varvec{2}}\right|}\) by the summand that corresponds to the constructions that exploit functions in \({n-4}\) variables. The comparison with other iterative bounds and lower bounds provided by some primary constructions is given in Table 3. Note that constructions C1, C2 can be build via the so-called indirect sum construction [8] of self-dual bent functions but it is difficult to estimate its cardinality for large n.
7 Decomposition of the form \(\left( f_0,f_1,f_2,f_3\right) \) for the general case
In this section the form and properties of the Gram matrix of an arbitrary bent function are considered.
It is interesting to study the conditions when the subfunctions \(f_0,f_1,f_2,f_3\) of the function itself and its dual are bent simultaneously. In current section we give an example of the property of the initial bent function that provides such double bentness.
7.1 General form of the Gram matrix
The form of the Gram matrix of a bent function and its dual one is characterized by the following
Theorem 6
The Gram matrices of any bent function, say f, in n variables and its dual bent function \(\widetilde{f}\) have form
where a, b, c are even integers such that
Proof
Recall the subsystem from the proof of Theorem 2, obtained via the inner products \(\left\langle 2\mathcal {H}R_i,2\mathcal {H}R_i\right\rangle \), \(i=0,1,2,3\):
This system has rank 3, its general solution is
for \(g_{12}\), \(g_{13}\) and \(g_{23}\) being free variables. Denote \(a=g_{12}\), \(b=-g_{23}\) and \(c=-g_{13}\), then we obtain the desired form of the Gram matrix:
We can also deduce that the Gram matrix of the dual function is strictly connected with the matrix of the function itself. Since the dual function \(\widetilde{f}\) is bent as well, it is enough to investigate the first row of its Gram matrix. We have
hence \({\left\langle R_0,R_1\right\rangle =c}\), \({\left\langle R_0,R_2\right\rangle =b}\) and \({\left\langle R_0,R_3\right\rangle =-a}\).
Now we are to point essential bounds on values of a, b and c and deduce some relations between them. In order to do it recall that any Gram matrix is positive semi-definite, hence all its eigenvalues must be nonnegative. The matrix \(\textrm{Gram}(f)\) has four eigenvalues, they are
One can note that these numbers are nonnegative if and only if
that is
and, consequently,
where \(|b|\) and \(|c|\) are essentially bounded by \(2^{n-2}\) from above. Parity of the numbers a, b, c comes from the fact that they are are inner products of integer vectors of an even dimension having odd coordinates. \(\square \)
Thus, the duality mapping acts on the Gram matrix by switching values of the coefficients b and c. One can show that these matrices are singular simultaneously and, moreover,
Corollary 4
The matrices \(\textrm{Gram}(f)\) and \(\textrm{Gram}\big (\widetilde{f}\big )\) have the same spectrum.
Theorem 6 can be reformulated in terms of Hamming distances between subfunctions:
Corollary 5
Let f be a bent function in n variables. The Hamming distances between \(\left\{ f_i\right\} _{i=0}^3\) are characterized by the matrix
for some positive integers \(d_1,d_2,d_3\) such that
Proof
The relation between the inner product and the Hamming distance yields the matrix whereas the inequalities are obtained from
with
\(\square \)
7.2 Linear dependence and bentness
In this subsection we are to consider the connection between singularity of the Gram matrix of an arbitrary bent function and bentness of its subfunctions.
We will need the following
Lemma 1
Let f and g be Boolean functions in even number k of variables, such that \({W_f(y),W_g(y)\in \big \{0,\pm 2^{k/2},\pm 2^{(k+2)/2}\big \}}\) for any \(y\in \mathbb {F}_2^k\) and
Then f and g are bent functions, moreover, it holds \(g=\widetilde{f}\).
Proof
Consider five nonnegative integers
Then we have the following system
where the second equation follows from the Parseval’s identity applied for the function g, and the third one is the product (12). The only nonnegative solution is
Hence, we have \({\left|W_f(y)\right|=2^{k/2}}\) for any \(y\in \mathbb {F}_2^k\).
By the same arguments one can show that \({\left|W_g(y)\right|=2^{k/2}}\) for any \(y\in \mathbb {F}_2^k\), therefore both of f and g are bent functions. Finally, it is enough to note that in this case the product (12) is exactly
that is \({\widetilde{f}=g}\). \(\square \)
For a bent function f with the Gram matrix \(\textrm{Gram}(f)\) the Gramian has the following expression
In Sect. 4.4 it was proved that the singularity of the Gram matrix of a self-dual bent function implies bentness of its subfunctions. It appears that this fact holds for any bent function as well.
Theorem 7
If the Gram matrix of a bent function f is singular, then subfunctions \(\{f_i\}_{i=0}^3\) are bent. Moreover, the subfunctions of \(\widetilde{f}\) are also bent.
Proof
It is enough to consider all such combinations of a, b, c that the Gramian (13) is zero. We will consider all the cases separately.
\({2^{n-2}-a+b-c=0}\): in terms of sign vectors it is equivalent to the following
From system (5) it follows that
that after simple transformations becomes
By Lemma 1 from the second equation we obtain that \(F_0\) and \(R_1\) are sign vectors of bent functions.
For other cases it is sufficient to list the systems, the rest of considerations are the same.
\({2^{n-2}-a-b+c=0}\):
\({2^{n-2}+a-b-c=0}\):
\({2^{n-2}+a+b+c=0}\):
\(\square \)
Again, from Theorem 7 and properties of the Gram matrix we conclude that
Corollary 6
If sign vectors of subfunctions \(\{f_i\}_{i=0}^3\) of a bent function f are linearly dependent, then these subfunctions are bent. Moreover, the subfunctions of \(\widetilde{f}\) are bent as well.
We can also consider \(4\times 4\) integer matrix, say M, with elements
In order to calculate its elements one can refer to the system (5) and consider inner products of equations with sign vectors of the subfunctions of f. The matrix \(\frac{1}{2}M\) is the following
It is clear that it is symmetric if and only if \(b=c\). This matrix provides one more condition for bentness of subfunctions.
Proposition 6
If matrix M of a bent function f is singular, then the subfunctions \(\{f_i\}_{i=0}^3\) are bent. Moreover, the subfunctions of \(\widetilde{f}\) are bent as well.
Proof
It is enough to straightly calculate the eigenvalues of the matrix M and consider cases when at least one of them is zero. The eigenvalues are
Note that \(\mu _3=-\lambda _3\) and \(\mu _4=\lambda _4\). The eigenvalues \(\mu _{1,2}\) are zero if and only if \({2^{n-2}-a=\left|b-c\right|}\), but it implies that either \(\lambda _1=0\) or \(\lambda _2=0\). So, in all cases we have that at least one of the eigenvalues of the matrix \(\textrm{Gram}(f)\) is zero, hence from Theorem 7 the result follows. \(\square \)
Thus, we obtain the properties of a matrix that consists of the inner products between sign vectors of subfunctions of a bent function and its dual. Whereas one of vectors is given in its Walsh–Hadamard transform.
8 Conclusion
In this work we studied the decompositions of the vector of values of a self-dual bent function and introduced the notation of the Gram matrix of a bent function. It is interesting to continue the study of this matrix and obtain new metrical relations between subfunctions of an arbitrary (self-dual) bent function. The search of the constructions of bent functions with particular Gram matrix is also a goal worth pursuing.
Subfunctions, considered in this work, were obtained by fixation of one or two first variables. We can also consider another way of choosing them, for instance by fixing some planes of dimension \(n-1\) and \(n-2\).
Considering the Gram matrices for the constructions C1 and C3 we can conclude that the problem of the classification of Gram matrices of self-dual bent functions (even in the case when all subfunctions are bent) comprises the problem of finding all values of the Rayleigh quotient that can be achieved by some of their subfunctions. The last problem has intersection with the investigation of the Hamming distances spectrum between bent functions and their duals.
Here we list main notation and results on the Gram matrix of a bent function, presented in current work:
References
Adams C.M., Tavares S.E.: Generating bent sequences. Discret. Appl. Math. 39, 155–159 (1992).
Bapić A., Pasalic E., Zhang F., Hodžić S.: Constructing new superclasses of bent functions from known ones. Cryptogr. Commun. 14(6), 1229–1256 (2022).
Canteaut A., Charpin P.: Decomposing bent functions. IEEE Trans. Inform. Theory 49(8), 2004–2019 (2003).
Canteaut A., Carlet C., Charpin P., Fontaine C.: On cryptographic properties of the cosets of \(R(1, m)\). IEEE Trans. Inform. Theory 47(4), 1494–1513 (2001).
Carlet C.: Two new classes of bent functions. In: Advances in Cryptology—EUROCRYPT ’93, pp. 77–101 Part of the Lecture Notes in Computer Science book series (LNCS, volume 765) (1994).
Carlet C.: Boolean Functions for Cryptography and Coding Theory (2020).
Carlet C., Mesnager S.: Four decades of research on bent functions. Des. Codes Cryptogr. 78(1), 5–50 (2016).
Carlet C., Danielsen L.E., Parker M.G., Solé P.: Self-dual bent functions. Int. J. Inf. Coding Theory 1, 384–399 (2010).
Climent J.-J., Garcia F.J., Requena V.: A construction of bent functions of \(n+2\) variables from a bent function of \(n\) variables and its cyclic shifts. Algebra 2014 (2014). Article ID 701298.
Cusick T.W., Stănică P.: Cryptographic Boolean Functions and Applications, 2nd edn. (2017).
Danielsen L.E., Parker M.G., Solé P.: The Rayleigh quotient of bent functions. In: Cryptography and Coding, pp. 418–432 Part of the Lecture Notes in Computer Science book series (LNCS, volume 5921) (2009).
Dillon J.: A survey of bent functions, pp. 191–215 (1972).
Dillon J.F.: Elementary Hadamard difference sets. PhD thesis, Univ. of Maryland (1974).
Feulner T., Sok L., Solé P., Wassermann A.: Towards the classification of self-dual bent functions in eight variables. Des. Codes Cryptogr. 68(1), 395–406 (2013).
Givens C.R.: Some observations on eigenvectors of Hadamard matrices of order \(2^n\). Linear Algebra Appl. 56, 245–250 (1984).
Hodžić S., Pasalic E., Wei Y.: A general framework for secondary constructions of bent and plateaued functions. Des. Codes Cryptogr. 88(10), 2007–2035 (2020).
Hodžić S., Pasalic E., Zhang W.: Generic constructions of five-valued spectra Boolean functions. IEEE Trans. Inform. Theory 65(11), 7554–7565 (2019).
Hou X.-D.: Classification of self dual quadratic bent functions. Des. Codes Cryptogr. 63(2), 183–198 (2012).
Hyun J.Y., Lee H., Lee Y.: MacWilliams duality and Gleason-type theorem on self-dual bent functions. Des. Codes Cryptogr. 63(3), 295–304 (2012).
Kutsenko A.V.: The Hamming distance spectrum between self-dual Maiorana-McFarland bent functions. J. Appl. Ind. Math. 12(1), 112–125 (2018).
Kutsenko A.: Metrical properties of self-dual bent functions. Des. Codes Cryptogr. 88(1), 201–222 (2020).
Kutsenko A.: The group of automorphisms of the set of self-dual bent functions. Cryptogr. Commun. 12(5), 881–898 (2020).
Kutsenko A., Tokareva N.: Metrical properties of the set of bent functions in view of duality. Appl. Discret. Math. 49, 18–34 (2020).
Kuz’min A.S., Markov V.T., Nechaev A.A., Shishkin V.A., Shishkov A.B.: Bent and hyper-bent functions over a field of \(2^l\) elements. Probl. Inf. Transm. 44(1), 12–33 (2008).
Li Y., Kan H., Mesnager S., Peng J., Tan C.H., Zheng L.: Generic constructions of (Boolean and vectorial) bent functions and their consequences. IEEE Trans. Inform. Theory 68(4), 2735–2751 (2022).
Logachev O.A., Sal’nikov A.A., Yashchenko V.V.: Bent functions on a finite abelian group. Discret. Math. Appl. 7(6), 547–564 (1997).
Luo G., Cao X., Mesnager S.: Several new classes of self-dual bent functions derived from involutions. Cryptogr. Commun. 11(6), 1261–1273 (2019).
MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes (1977).
Mesnager S.: Bent Functions: Fundamentals and Results (2016).
Mesnager S.: On semi-bent functions and related plateaued functions over the Galois field \(\mathbb{F} _{2^n}\), pp. 243–273 (2014).
Mesnager S.: Several new infinite families of bent functions and their duals. IEEE Trans. Inform. Theory 60(7), 4397–4407 (2014).
Pasalic E., Bapić A., Zhang F., Wei Y.: Explicit infinite families of bent functions outside the completed Maiorana-McFarland class. Des. Codes Cryptogr. 91(7), 2365–2393 (2023).
Preneel B., Van Leekwijck W., Van Linden L., Govaerts R., Vandewalle J.: Propagation characteristics of Boolean functions. In: Advances in Cryptology—EUROCRYPT ’90, pp. 161–173 (LNCS, volume 473) (1991).
Rifá J., Zinoviev V.A.: On binary quadratic symmetric bent and almost bent functions. arXiv:1211.5257v3.
Rothaus O.S.: On “bent’’ functions. J. Comb. Theory Ser. A. 20(3), 300–305 (1976).
Shi M., Li Y., Cheng W., Crnković D., Krotov D., Solé P.: Self-dual bent sequences for complex Hadamard matrices. Des. Codes Cryptogr. 91(4), 1453–1474 (2023).
Shi M., Li Y., Cheng W., Crnković D., Krotov D., Solé P.: Self-dual Hadamard bent sequences. J. Syst. Sci. Complex 36(2), 894–908 (2023).
Su S., Guo X.: A further study on the construction methods of bent functions and self-dual bent functions based on Rothaus’s bent function. Des. Codes Cryptogr. 91(4), 1559–1580 (2023).
Tang C., Zhou Z., Qi Y., Zhang X., Fan C., Helleseth T.: Generic construction of bent functions and bent idempotents with any possible algebraic degrees. J. Pure Appl. Algebra 63(10), 6149–6157 (2017).
Tokareva N.: On the number of bent functions from iterative constructions: lower bounds. Adv. Math. Commun. 5(4), 609–621 (2011).
Tokareva N.: Bent Functions: Results and Applications to Cryptography (2015).
Wolfmann J.: Special bent and near-bent functions. Adv. Math. Commun. 8(1), 21–33 (2014).
Yarlagadda R., Hershey J.: A note on the eigenvectors of Hadamard matrices of order \(2^n\). Linear Algebra Appl. 45, 43–53 (1982).
Acknowledgements
The work was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. FWNF-2022-0018).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by G. Kyureghyan.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Kutsenko, A. Decomposing self-dual bent functions. Des. Codes Cryptogr. 92, 113–144 (2024). https://doi.org/10.1007/s10623-023-01298-2
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-023-01298-2