1 Introduction
Bent functions were introduced by Rothaus [23], as a particular class of Boolean functions that has many interesting connections to other combinatorial objects such as Hadamard matrices and difference sets. Their applications in cryptography come in the first place from their characterization as a class of Boolean functions achieving the highest nonlinearity possible (thus being at the largest distance to the set of affine functions). A survey article [8] describes the main properties and construction methods related to bent functions, whereas their detailed study is given in the book of Mesnager [21]. On the other hand, for the applications of Boolean functions in cryptography we refer to the textbooks of Carlet [7] and Cusick and Stanica [11].
Two known primary classes of bent functions are the Maiorana–McFarland (\({{{\mathcal {M}}}{{\mathcal {M}}}}\)) class and the Partial Spreads (\({{\mathcal {P}}}{{\mathcal {S}}}\)) class, which were introduced in the 1970s in [19] and [12], respectively. Since it is not a simple matter to construct elements of the \({{\mathcal {P}}}{{\mathcal {S}}}\) class practically, an explicit subclass of \({{\mathcal {P}}}{{\mathcal {S}}}\), denoted by \({{\mathcal {P}}}{{\mathcal {S}}}_{ap}\), was specified by Dillon in [13]. It seems quite unrealistic that other primary classes are yet to be discovered and therefore many secondary constructions (using known bent functions to build possibly new ones) have been proposed in the literature. A non-exhaustive list of various secondary constructions can be found in the following works [4, 6, 9, 16, 20, 24, 30]. However, the question regarding the class inclusion of bent functions stemming from these secondary construction methods is commonly left open, apart from a few works [1, 4, 18, 20, 26‐28] where some explicit families of bent functions provably outside the completed \({{{\mathcal {M}}}{{\mathcal {M}}}}\) class are given. The main purpose of this article is to address the class inclusion more properly and thus also to contribute to a classification of bent functions. Nevertheless, the problem of finding efficient indicators for the inclusion/exclusion in the completed \({{\mathcal {P}}}{{\mathcal {S}}}\) class remains unanswered. This problem is equivalent to finding cliques in a graph which is known to be NP-hard, see also [10, p. 43].
Advertisement
In this article, we employ a fundamental result (though not stated explicitly in the literature) concerning the inclusion in the completed \({{{\mathcal {M}}}{{\mathcal {M}}}}\) class (denoted \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\)), which involves the dual function of a given bent function. More precisely, it can be shown that a bent function f is in/outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) if and only if its bent dual is in/outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). This result also implies that given a single bent function outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) (or alternatively its dual) one essentially derives a whole equivalence class whose members are also outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). To verify these results practically, we also propose a rather simple algorithm for determining the inclusion in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). The algorithm uses the graph-theoretic notion of a clique (complete subgraph) to implement the second-order derivative criterion of Dillon [12], commonly used when determining the inclusion/exclusion in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). Its performance is quite satisfactory, allowing us to test the class inclusion for up to 12 variables efficiently. The above mentioned fact regarding a bent function and its dual (with respect to the inclusion in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\)) is then useful when the so-called 4-decomposition of bent functions (say on \({\mathbb {F}}_2^n\)) is considered, which regards the decomposition into the cosets of an \((n-2)\)-dimensional subspace V of \({\mathbb {F}}_2^n\). It was originally investigated by Canteaut and Charpin [3] in terms of the second-order derivatives of the dual function, whereas the similar properties were recently stated using duals of the cosets of V [14]. The main conclusion in [3] is that there are exactly three possible cases of this 4-decomposition of a bent function, namely, all four restrictions being bent, semi-bent, or 5-valued spectra functions. For each of the cases, using the necessary and sufficient conditions in [14] (see Theorem 2.2), we provide generic methods (at least one) for designing bent functions provably outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). For instance, in the elementary case of defining a bent function \(h(\textbf{x},y_1,y_2)=f(\textbf{x}) \oplus y_1y_2\) on \({\mathbb {F}}_2^{n+2}\) using any bent function f on \({\mathbb {F}}_2^n\) (corresponding to a bent 4-decomposition since \(h=f||f||f||(1\oplus f)\)), we show that h is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) if and only if f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). In this context, we also refer to [2] where four different (specific) bent functions \(f_1, \ldots ,f_4\) were used for the same purpose. This approach is then generalized to the case when two bent functions are used. More precisely, the concatenation \(f_1||f_1||f_2||(1\oplus f_2)\) also gives bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) if \(f_1\) or \(f_2\) is a bent function outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). This also naturally leads to a recursive construction of bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) on larger ambient spaces.
The cases when the four restrictions of a bent function are semi-bent or 5-valued spectra functions are also considered and several design methods of designing infinite families of bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) are proposed. We remark that the cardinality of bent functions that are provably outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) is extremely large which is also emphasized for instance in Remark 3.4, where a single dual bent function on \({\mathbb {F}}_2^8\) which is not in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) gives rise to the EA-equivalence class comprising \(\approx 2^{70}\) bent functions on \({\mathbb {F}}_2^{12}\) that are not in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) as well. This only concerns our design method of concatenating four suitable semi-bent functions (using a dual which is not in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\)), however our other constructions are similar in this context. Most notably, it seems that the presence of linear structures in these semi-bent functions (being restrictions of a bent function) is of no relevance for the class inclusion. More precisely, the use of a dual bent function outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\), whose relaxed linearity index (see Definition 3.1) is of certain order, for their specification is sufficient for ensuring that the resulting bent function is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) as well. A similar conclusion is valid when a sophisticated notion of duals of 5-valued spectra functions is employed for the same purpose, see for instance Theorem 3.7. Again, having a bent dual outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) ensures that the concatenation of four suitably selected 5-valued spectra functions generates bent functions that do not belong to \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) (regardless of the presence of linear structures in these constituent functions).
The rest of this paper is organized as follows. In Sect. 2, we give some basic definitions related to Boolean functions and discuss the concept of dual functions for some important classes of Boolean functions.
The design of bent functions provably outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) is addressed in Sect. 3. More precisely, we provide construction methods for specifying suitable quadruples of bent, semi-bent and 5-valued spectra functions so that the resulting bent functions are provably outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). In Sect. 4, we consider the design of bent functions by selecting 5-valued spectra functions in the generalized Maiorana-McFarland class. However, it remains an open problem whether this approach can generate bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). Some concluding remarks are given in Sect. 5.
Advertisement
2 Preliminaries
We denote the Galois field of order \(2^n\) by \({\mathbb {F}}_{2^n}\) and the corresponding vector space by \({\mathbb {F}}_2^n\) which contains binary n-tuples \(\mathbf {\textbf{x}}=(x_1,\ldots ,x_n)\), where \(x_i \in {\mathbb {F}}_2\). A mapping \(f: {\mathbb {F}}_2^n \rightarrow {\mathbb {F}}_2\) is called an n-variable Boolean function and we use \({\mathcal {B}}_n\) to denote the set of all possible Boolean mappings on \({\mathbb {F}}_2^n\). Any Boolean function \(f:{\mathbb {F}}_2^n \rightarrow {\mathbb {F}}_2\) can be represented using the so-called algebraic normal form (ANF), so thatwhere \(x_i, \lambda _{\mathbf {\mathbf {\textbf{u}}}} \in {\mathbb {F}}_2\) and \(\mathbf {\mathbf {\textbf{u}}}=(u_1, \ldots ,u_n)\in {\mathbb {F}}^n_2\) and we reserve the symbol “\(\bigoplus \)” to denote the addition modulo two. Then, the algebraic degree of f, denoted by deg(f) or sometimes simply d, is the maximal value of the Hamming weight of \(\mathbf {\textbf{u}}\) such that \(\lambda _{\mathbf {\textbf{u}}}\ne 0\). Throughout this article we will use \({{\textbf {0}}}_n\) to denote the all-zero vector with n coordinates, that is \((0,0,\ldots ,0)\in {\mathbb {F}}^n_2.\)
$$\begin{aligned} f(x_1,\ldots ,x_n)=\bigoplus _{\mathbf {\mathbf {\textbf{u}}}\in {\mathbb {F}}^n_2}{\lambda _{\mathbf {\mathbf {\textbf{u}}}}}{\left( \prod _{i=1}^n{x_i}^{u_i}\right) }, \end{aligned}$$
(1)
Another useful representation of \(f\in {\mathcal {B}}_n\) is its evaluation on \({\mathbb {F}}^n_2\) (known as the truth table) and defined aswhose corresponding \((\pm 1)\)-sequence of f is given asThe Hamming distance \(d_H\) between two arbitrary Boolean functions, say \(f,g\in {\mathcal {B}}_n,\) is defined bywhere \(\chi _f\cdot \chi _g=\sum _{\textbf{x}\in {\mathbb {F}}^n_2}(-1)^{f(\textbf{x})\oplus g(\textbf{x})}\). In general, the standard inner (dot) product of two vectors \(\mathbf {\textbf{x}}=(x_1,\ldots ,x_n)\) and \(\mathbf {\textbf{y}}=(y_1,\ldots ,y_n)\) in \({\mathbb {F}}_2^n\) is defined as \(\mathbf {\textbf{x}}\cdot \mathbf {\textbf{y}}=x_1 y_1\oplus \cdots \oplus x_n y_n.\)
$$\begin{aligned} T_f=(f(0,\ldots ,0,0),f(0,\ldots ,0,1),\ldots ,f(1,\ldots ,1,1)), \end{aligned}$$
$$\begin{aligned} \chi _f=((-1)^{f(0,\ldots ,0,0)},(-1)^{f(0,\ldots ,0,1)},\ldots , (-1)^{f(1,\ldots ,1,1)}). \end{aligned}$$
$$\begin{aligned} d_H(f,g)=\{\textbf{x}\in {\mathbb {F}}^n_2:f(\textbf{x})\ne g(\textbf{x})\}=2^{n-1}-\frac{1}{2}\chi _f\cdot \chi _g, \end{aligned}$$
The Walsh–Hadamard transform (WHT) of \(f\in {\mathcal {B}}_n\), at any point \({\varvec{\omega }}\in {\mathbb {F}}^n_2\) is defined asGiven the Walsh spectrum of a function \(f\in {\mathcal {B}}_n\), its truth table can be recovered using the inverse WHT given byA function \(f\in {\mathcal {B}}_n,\) for even n, is called bent if \(W_f(\mathbf {\mathbf {\textbf{u}}})=\pm 2^{\frac{n}{2}}\). We further note that for a bent function \(f\in {\mathcal {B}}_n\), we have \(W_f(\mathbf {\mathbf {\textbf{u}}})=(-1)^{f^*(\mathbf {\mathbf {\textbf{u}}})}2^{\frac{n}{2}}\) for a Boolean function \(f^*\in {\mathcal {B}}_n\). This function \(f^*\) is called the dual of f and is also a bent function.
$$\begin{aligned} W_{f}({\varvec{\omega }})=\sum _{\textbf{x}\in {\mathbb {F}}_2^n}(-1)^{f(\textbf{x})\oplus \varvec{\omega }\cdot \textbf{x}}. \end{aligned}$$
(2)
$$\begin{aligned} (-1)^{f(\textbf{x})}=2^{-n}\sum _{\varvec{\omega }\in {\mathbb {F}}_2^n}W_f({\varvec{\omega }})(-1)^{\varvec{\omega }\cdot \textbf{x}}. \end{aligned}$$
(3)
The first-order derivative of \(f \in {\mathcal {B}}_n\) at \(\textbf{a} \in {\mathbb {F}}_2^n\), denoted by \(D_{\textbf{a}}f\), is the Boolean function defined byIn particular, \(f:{\mathbb {F}}_2^{n} \rightarrow {\mathbb {F}}_{2}\) is said to admit a linear structure \(\varvec{\gamma } \in {\mathbb {F}}_{2}^{n*}\) if \(D_{\varvec{\gamma }}f(\textbf{x})=f(\textbf{x}\oplus \varvec{\gamma })\oplus f(\textbf{x})=c\) for all \(\textbf{x} \in {\mathbb {F}}_2^n\), where \(c \in {\mathbb {F}}_2\).
$$\begin{aligned} D_{\textbf{a}}f(\textbf{x}) = f(\textbf{x} \oplus \textbf{a}) \oplus f(\textbf{x}), \text{ for } \text{ all } \textbf{x} \in {\mathbb {F}}_2^n. \end{aligned}$$
The Maiorana–McFarland class \({{{\mathcal {M}}}{{\mathcal {M}}}}\) is the set of n-variable (n is even) Boolean functions of the formwhere \(\pi \) is a permutation on \({\mathbb {F}}_2^{n/2}\), and g is an arbitrary Boolean function on \({\mathbb {F}}_2^{n/2}\). In general, the completed class is obtained by applying the so-called extended affine (EA) equivalence to all the functions in a given class. Since we are mainly interested in the class \({{\mathcal {M}}}{{\mathcal {M}}}\), its completed version \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) is defined as,where \(GL(n,{\mathbb {F}}_2)\) denotes the group of invertible matrices under composition. The following lemma, originally due to Dillon [12] and later extended by Carlet [7, Proposition 54, pp. 167] to (easily) cover the other direction, is of crucial importance for the discussion on class inclusion.
$$\begin{aligned} f(\textbf{x},\textbf{y})=\textbf{x} \cdot \pi (\textbf{y})\oplus g(\textbf{y}), \text{ for } \text{ all } \textbf{x}, \textbf{y} \in {\mathbb {F}}_2^{n/2}, \end{aligned}$$
(4)
$$\begin{aligned} {{\mathcal {M}}}{{\mathcal {M}}}^\#=\{f(A\textbf{x}\oplus \textbf{b}) \oplus \textbf{c} \cdot \textbf{x} \oplus d: f \in {{\mathcal {M}}}{{\mathcal {M}}}, A \in GL(n,{\mathbb {F}}_2), \textbf{b}, \textbf{c} \in {\mathbb {F}}_2^n, d \in {\mathbb {F}}_2\}, \end{aligned}$$
Lemma 2.1
[12, p. 102] [7, Proposition 54, pp. 167] A bent function f in n variables belongs to \({{\mathcal {M}}}{{\mathcal {M}}}^{\#}\) if and only if there exists an \(\frac{n}{2}\)-dimensional linear subspace V of \({\mathbb {F}}_2^n\) such that the second-order derivatives, defined byvanish for any \( \textbf{a}, \textbf{b} \in V\).
$$\begin{aligned} D_{\textbf{a}}D_{\textbf{b}}f(\textbf{x})=f(\textbf{x})\oplus f(\textbf{x}\oplus \textbf{a})\oplus f(\textbf{x}\oplus \textbf{b})\oplus f(\textbf{x}\oplus \textbf{a}\oplus \textbf{b}), \end{aligned}$$
2.1 Plateaued functions and their duals
A function \(f\in {\mathcal {B}}_n\) is called s-plateaued if its Walsh spectra only takes three values 0 and \(\pm 2^{\frac{n+s}{2}}\) (the value \(2^{\frac{n+s}{2}}\) is called the amplitude), where \(s\ge 1\) if n is odd and \(s\ge 2\) if n is even (s and n always have the same parity). In particular, a class of 1-plateaued functions for n odd, or 2-plateaued for n even, corresponds to so-called semi-bent functions. The Walsh support of \(f\in {\mathcal {B}}_n\) is defined as \(S_f=\{{\varvec{\omega }}\in {\mathbb {F}}^n_2\;:\; W_f({\varvec{\omega }})\ne 0\}\) and for an s-plateaued function its cardinality is \(\#S_f=2^{n-s}\) [3, Proposition 4].
We define a dual function \(f^*:S_f \rightarrow {\mathbb {F}}_2\) of an s-plateaued function \(f \in {\mathcal {B}}_n\) using \(W_f({\varvec{\omega }})=2^{\frac{n+s}{2}}(-1)^{f^*({\varvec{\omega }})},\) for \({\varvec{\omega }}\in S_f \subset {\mathbb {F}}_2^n\). To specify the dual function as \({\overline{f}}^*:{{\mathbb {F}}}_{2}^{n-s} \rightarrow {{\mathbb {F}}}_{2}\), we use the concept of lexicographic ordering. That is, a subset \(E=\{\textbf{e}_0,\ldots ,\textbf{e}_{2^{n-s}-1}\}\subset {\mathbb {F}}^{n}_2\) is ordered lexicographically if \(|\textbf{e}_i| < |\textbf{e}_{i+1}|\) for any \(i \in [0,2^{n-s}-2]\), where \(|\textbf{e}_i|= \sum _{j=0}^{n-1}\textbf{e}_{i,n-1-j} 2^j\) denotes the integer representation of \(\textbf{e}_i \in {\mathbb {F}}^n_2\). Since \(S_f\) is not ordered in general, we will always represent it as \(S_f=\textbf{v}\oplus E\), where E is lexicographically ordered for some fixed \(\textbf{v}\in S_f\) and \(\textbf{e}_0={{\textbf {0}}}_{n}\), thus E is a linear subspace of dimension \(n-s\).
A direct correspondence between \({{\mathbb {F}}}_{2}^{n-s}\) and \(S_f=\{{\varvec{\omega }}_0,\ldots ,{\varvec{\omega }}_{2^{n-s}-1}\}\) is achieved through E, so that for the lexicographically ordered \({{\mathbb {F}}}_{2}^{n-s}=\{\textbf{x}_0, \textbf{x}_1, \ldots , \textbf{x}_{2^{n-s}-1}\}\) we havewhere \(\textbf{x}_i \in {{\mathbb {F}}}_{2}^{n-s}, \; \textbf{e}_i \in E,\;i\in [0,2^{n-s}-1]\).
$$\begin{aligned} {\overline{f}}^*(\textbf{x}_i)=f^*(\textbf{v}\oplus \textbf{e}_i)=f^*({\varvec{\omega }}_i), \end{aligned}$$
(5)
Remark 2.1
Throughout this article, from the design perspective, the dual of an s-plateaued function \(f:{\mathbb {F}}^n_2\rightarrow {\mathbb {F}}_2\) will be denoted by \(f^*\) and is considered as a function on \(S_f\) (that is \(f^*:S_f\rightarrow {\mathbb {F}}_2\)). However, as specified in (5), the notation \({\overline{f}}^*\) associates this dual to a function defined on \({\mathbb {F}}^{n-s}_2\), that is \({\overline{f}}^*:{\mathbb {F}}^{n-s}_2\rightarrow {\mathbb {F}}_2\).
The main reason for ordering the elements in E lexicographically is Theorem 3.3 (that essentially follows from Lemma 3.1 in [16]), given originally in [15] and recalled in Sect. 3.3.1, which from the design perspective gives the conditions on \(S_f\) so that the spectral values defined through \(f^*\) (or \({\overline{f}}^*\)) indeed specify a valid Walsh spectrum of a Boolean function. Furthermore, it was noted in [17] that different orderings of \(S_f\), both with respect to the choice of \({{\varvec{v}}}\) so that \(S_f={\varvec{v}} \oplus E\) as well as representing it differently so that \(S_f={{\varvec{v}}}' \oplus E'\) (with \({{\varvec{v}}} \ne {{\varvec{v}}}'\) and \(E \ne E'\)), essentially give affine equivalent duals \({\overline{f}}^*\) and \(\overline{f'}^*\), see Section 5 in [17] for further details. Nevertheless, all these results use the assumption that item (i) in Lemma 3.1 in [16] is satisfied. Namely, an m-dimensional linear subspace \(E=\{\textbf{e}_0, \textbf{e}_1, \ldots , \textbf{e}_{2^m-1}\}\) is “suitably” ordered to be used in Theorem 3.3 whenever for any fixed \(i \in \{0, \ldots , m-1\}\) it holds that \(\textbf{e}_j = \textbf{e}_{2^i} \oplus \textbf{e}_{j-2^i}\), for all \(2^i \le j \le 2^{i+1}-1\). In the case of lexicographic ordering this recursion is satisfied.
In this context, we recall one essential result on the properties of the dual plateaued functions for different representations of \(S_f\). We remark that an s-plateaued function on \({\mathbb {F}}_2^n\) is called trivial if its Walsh support is an affine subspace.
Theorem 2.1
[15] Let \(f,h:{\mathbb {F}}^n_2\rightarrow {\mathbb {F}}_2\) be two trivial s-plateaued functions whose Walsh supports are related as \(S_h=\textbf{c} \oplus S_fM\), for some matrix \(M\in GL(n,{\mathbb {F}}_2)\) and \(\textbf{c} \in {\mathbb {F}}^n_2.\) Representing \(S_f=\textbf{v}\oplus E=\{{\varvec{\omega }}_i=\textbf{v}\oplus \textbf{e}_i:\textbf{e}_i\in E\}\) for a lexicographically ordered linear space \(E=\{\textbf{e}_0,\ldots , \textbf{e}_{2^{n-s}-1}\}\), let the functions \({\overline{f}}^*\) and \({\overline{h}}^*\) be defined aswhere \(\textbf{z}_i=c \oplus {\varvec{\omega }}_iM\in S_h\). Then, f and h are EA-equivalent if and only if their duals \({\overline{f}}^*,{\overline{h}}^*:{\mathbb {F}}^{n-s}_2\rightarrow {\mathbb {F}}_2\) are EA-equivalent bent functions.
$$\begin{aligned} {\overline{f}}^*(\textbf{x}_i)=f^*({\varvec{\omega }}_i)\;\;\;\text {and}\;\;\;{\overline{h}}^*(\textbf{x}_i)=h^*(\textbf{z}_i),\;\;\;(i\in [0,2^{n-s}-1]), \end{aligned}$$
2.2 Specifying 5-valued spectra functions through duals
We first recall certain notations, introduced in [14] and also used in [17], useful in handling a 5-valued spectra Boolean function which has two different non-zero absolute values.
Let the WHT spectrum of a function \(f:{\mathbb {F}}^n_2\rightarrow {\mathbb {F}}_2\) contain the values \(0,\pm c_1,\pm c_2\) (\(c_1\ne c_2\)), where \(c_1,c_2\in {\mathbb {N}}\). Some of the results in [14] are stated in a more general context, but since the 4-decomposition of bent functions is our main objective we only consider the cases \(c_1=2^{n/2}\) and \(c_2=2^{(n+2)/2}\) above. For \(i=1,2\), by \(S^{[i]}_f\subset {\mathbb {F}}^n_2\) we denote the set \(S^{[i]}_f=\{\mathbf {\mathbf {\textbf{u}}}\in {\mathbb {F}}^n_2:|W_f(\mathbf {\mathbf {\textbf{u}}})|=c_i\}\), and we can define the functions \(f^*_{[i]}:S^{[i]}_f\rightarrow {\mathbb {F}}_2\) such that the following equality holds:For \(i=1,2\), let \(\textbf{v}_i\in {\mathbb {F}}^n_2\) and \(E_i=\{\textbf{e}^{(i)}_0,\ldots ,\textbf{e}^{(i)}_{2^{\lambda _i}-1}\}\subset {\mathbb {F}}^n_2\) (\(\textbf{e}^{(i)}_0={{\textbf {0}}}_n\)) be lexicographically ordered subsets of cardinality \(2^{\lambda _i}\) such that \(S^{[i]}_f=\{{\varvec{\omega }}^{(i)}_0,\ldots ,{\varvec{\omega }}^{(i)}_{2^{\lambda _i}-1}\}=\textbf{v}_i\oplus E_i\), where \({\varvec{\omega }}^{(i)}_j=\textbf{v}_i\oplus \textbf{e}^{(i)}_j\), for \(j\in [0,2^{\lambda _i}-1]\). Clearly, the lexicographically ordered set \(E_i\) imposes an ordering on \(S^{[i]}_f\) with respect to the equality \({\varvec{\omega }}^{(i)}_j=\textbf{v}_i\oplus \textbf{e}^{(i)}_j\). Using the representation of \(S^{[i]}_f=\textbf{v}_i\oplus E_i\) and the fact that the cardinality of \(S^{[i]}_f\) is a power of two, the function \({\overline{f}}^*_{[i]}\), as a mapping from \({\mathbb {F}}^{\lambda _i}_2\) to \({\mathbb {F}}_2\), is defined aswhere \({\mathbb {F}}^{\lambda _i}_2=\{\textbf{x}_0,\ldots ,\textbf{x}_{2^{\lambda _i}-1}\}\) is ordered lexicographically.
$$\begin{aligned} W_f(\mathbf {\mathbf {\textbf{u}}})=\left\{ \begin{array}{ll} 0, &{} \mathbf {\mathbf {\textbf{u}}}\not \in S^{[1]}_f\cup S^{[2]}_f, \\ c_i\cdot (-1)^{f^*_{[i]}(\mathbf {\mathbf {\textbf{u}}})}, &{} \mathbf {\mathbf {\textbf{u}}}\in S^{[i]}_f,\;\; i\in \{1,2\}.\\ \end{array} \right. \end{aligned}$$
(6)
$$\begin{aligned} {\overline{f}}^*_{[i]}(\textbf{x}_j)=f^*_{[i]}(\textbf{v}_i\oplus \textbf{e}^{(i)}_j)=f^*_{[i]}({\varvec{\omega }}^{(i)}_j),\;\;j\in [0,2^{\lambda _i}-1], \end{aligned}$$
(7)
A more specific method for designing 5-valued spectra functions on \({\mathbb {F}}_2^n\) (thus \(W_{f}(\mathbf {\mathbf {\textbf{u}}})\in \{0,\pm 2^{n/2},\pm 2^{\frac{n+2}{2}} \}\)), originally considered in [14], will be used in Sect. 3.4 for specifying suitable quadruples of such functions whose concatenation will give bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\).
2.3 Decomposition of bent functions
In [3], Canteaut and Charpin considered the decomposition of bent functions on \({{\mathbb {F}}}_{2}^n\), \(n \ge 4\) is even, with respect to affine subspaces \(\textbf{a}\oplus V\), for some k-dimensional linear subspace \(V\subset {\mathbb {F}}^n_2\). In general, this decomposition of \({\mathfrak {f}} \in {\mathcal {B}}_n\) can be viewed as a collection of \(2^{n-k}\) Boolean functions denoted by \({\mathfrak {f}}_{\textbf{a}\oplus V}\) and defined on \({{\mathbb {F}}}_{2}^k \rightarrow {\mathbb {F}}_2\) usingfor lexicographically ordered \(V=\{\textbf{v}_0,\ldots ,\textbf{v}_{2^k-1}\}\) and \({\mathbb {F}}^k_2=\{\textbf{x}_0,\ldots ,\textbf{x}_{2^k-1}\}\). This identification between V and \({\mathbb {F}}^k_2\), and thus the definition of \({\mathfrak {f}}_{\textbf{a}\oplus V}:{\mathbb {F}}^k_2\rightarrow {\mathbb {F}}_2\), strongly depends on the ordering of V in a similar sense as mentioned in Sect. 2.
$$\begin{aligned} {\mathfrak {f}}_{\textbf{a}\oplus V}(\textbf{x}_i)={\mathfrak {f}}_{\textbf{a}\oplus V}(\textbf{a}\oplus \textbf{v}_i),\;\;\;i\in [0,2^k-1], \end{aligned}$$
(8)
Since in this article we are mainly interested in the design methods of bent functions on \({\mathbb {F}}_2^n\) using a concatenation of four functions on \({\mathbb {F}}_2^{n-2}\), we will consider V to be an \((n-2)\)-dimensional subspace of \({\mathbb {F}}_2^n\). Hence, the functions \(f_1, \ldots , f_4 \in {\mathcal {B}}_{n-2}\) can be defined on the four cosets \({{\textbf {0}}}_n\oplus V, \textbf{a} \oplus V,\textbf{b} \oplus V,(\textbf{a} \oplus \textbf{b}) \oplus V\) respectively, for an arbitrary linear subspace V of dimension \(n-2\) so that \(Q=\langle \textbf{a}, \textbf{b} \rangle \) and \(Q\oplus V={\mathbb {F}}^n_2\) (with \(Q\cap V=\{{{\textbf {0}}}_n\}\)). We will denote such a decomposition as \({\mathfrak {f}}=(f_1,f_2,f_3,f_4)_V\), where \({\mathfrak {f}} \in {\mathcal {B}}_n\) and \(f_i \in {\mathcal {B}}_{n-2}\). However, specifying \(V={\mathbb {F}}_2^{n-2} \times (0,0)\) we have the canonical decomposition which we simply denote as \({\mathfrak {f}}=(f_1,f_2,f_3,f_4)\). Following the terminology in [3], this decomposition is said to be a bent 4-decomposition when all \(f_i\) (\(i\in [1,4]\)), are bent; a semi-bent 4-decomposition when all \(f_i\) (\(i\in [1,4]\)) are semi-bent; a 5-valued 4-decomposition when all \(f_i\) (\(i\in [1,4]\)) are 5-valued spectra functions so that \(W_{f_i} \in \{0, \pm 2^{(n-2)/2}, \pm 2^{n/2}\} \).
The 4-decomposition was fully described in [3] in terms of the second-order derivatives (with respect to \(\textbf{a}\) and \(\textbf{b}\)) of the dual \({\mathfrak {f}}^*\) of a bent function \( {\mathfrak {f}}\). Alternatively, the approach that will be used in this article, this decomposition can be specified in terms of Walsh supports and duals of its restrictions \(f_{1},\ldots ,f_4\) [14]. Note that functions \(f_i\) are considered as functions in \((n-2)\)-variables in terms of Eq. (8) (that is when \(\dim (V)=k=n-2\)).
Theorem 2.2
[14] Let \({\mathfrak {f}} \in {\mathcal {B}}_n\) be a bent function, for even \(n \ge 4\). Let \(\textbf{a}, \textbf{b} \in {{\mathbb {F}}_2^n}{\setminus } \{{{\textbf {0}}}_n\}\) \((\textbf{a}\ne \textbf{b})\) and V a linear subspace of \({\mathbb {F}}_2^n\) with \(\dim (V)=n-2\) so that \(\langle \textbf{a}, \textbf{b}\rangle \oplus V ={\mathbb {F}}_2^n\). If we denote by \((f_1,\ldots ,f_4)\) the 4-decomposition of \({\mathfrak {f}}\) with respect to V, then \((f_1,\ldots ,f_4)\) is:
(i)
A bent 4-decomposition if and only if it holds that \(f^*_1\oplus f^*_2\oplus f^*_3\oplus f^*_4=1\).
(ii)
A semi-bent 4-decomposition if and only if functions \(f_i\) \((i\in [1,4])\) are pairwise disjoint spectra semi-bent functions.1
(iii)
A five-valued 4-decomposition if and only if the following statements hold:
(a)
The sets \(S^{[1]}_{f_i}=\{{\varvec{\vartheta }}\in {\mathbb {F}}^{n-2}_2:|W_{f_i}({\varvec{\vartheta }})|=2^{\frac{n}{2}}\}\) \((i\in [1,4])\) are pairwise disjoint;
(b)
All \(S^{[2]}_{f_i}=\{{\varvec{\vartheta }}\in {\mathbb {F}}^{n-2}_2:|W_{f_i}({\varvec{\vartheta }})|=2^{\frac{n-2}{2}}\}\) are equal \((i\in [1,4])\), and for \(f^*_{[2],i}:S^{[2]}_{f_i}\rightarrow {\mathbb {F}}_2\) it holds that \(f^*_{[2],1}\oplus f^*_{[2],2}\oplus f^*_{[2],3}\oplus f^*_{[2],4}=1\).
In the rest of this article, we consider the canonical 4-decomposition so that \(\textbf{a}=(0,0,\ldots ,0,1)\), \(\textbf{b}=(0,0,\ldots ,1,0) \in {\mathbb {F}}_2^n\) and consequently \(V={\mathbb {F}}_2^{n-2} \times \{(0,0)\}\) in Theorem 2.2. Then, the function \({\mathfrak {f}}\) is the concatenation of \(f_i \in {\mathcal {B}}_{n-2}\) which we denote by \({\mathfrak {f}}=f_1||f_2||f_3||f_4\). Using the convention that \({\mathfrak {f}}(\textbf{x},0,0)=f_1(\textbf{x}), {\mathfrak {f}}(\textbf{x},0,1)=f_2(\textbf{x}), {\mathfrak {f}}(\textbf{x},1,0)=f_3(\textbf{x})\) and \({\mathfrak {f}}(\textbf{x},1,1)=f_4(\textbf{x})\), the ANF of \({\mathfrak {f}}=f_1||f_2||f_3||f_4\) is given by
$$\begin{aligned} {\mathfrak {f}}(\textbf{x},y_1,y_2)=f_1(\textbf{x})\oplus y_1(f_1\oplus f_3)(\textbf{x})\oplus y_2(f_1\oplus f_2)(\textbf{x})\oplus y_1y_2(f_1\oplus f_2\oplus f_3\oplus f_4)(\textbf{x}). \nonumber \\ \end{aligned}$$
(9)
3 Decomposing bent functions: design methods
From the design perspective, Theorem 2.2 allows us to specify (possibly new) bent functions by specifying suitable quadruples of bent, semi-bent, or 5-valued spectra functions. We develop these ideas below more precisely in the rest of this section, but before this we propose an efficient algorithm for testing the inclusion in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). Throughout this article, due to the fact that all bent functions up to six variables are contained in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\), we will consider the design of bent functions on \({\mathbb {F}}_2^n\), where \(n \ge 8\) is even.
3.1 An algorithm for determining whether \(f \in {{{\mathcal {M}}}{{\mathcal {M}}}}^\#\)
We first describe an algorithmic approach to determine whether a bent function is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). The algorithm is based on Lemma 2.1 and some graph-theoretical concepts.
Let \(f\in {\mathcal {B}}_n\) be a bent function. Set \(\Gamma =(V,E)\) to be a graph with edge setand vertex set \(V\subset {{\mathbb {F}}_2^{n}}^*\) consisting of all distinct vertices appearing in the edge set E. For simplicity, we do not add 0 to V as \(D_0D_\textbf{b}f\equiv 0\) for all \(\textbf{b}\in {\mathbb {F}}_2^{n}\). With this approach, we reduce the size of the vertex set V as \(D_{{\varvec{a}}}D_{{\varvec{b}}}f\not \equiv 0\), for some \(\textbf{a},\textbf{b}\in {{\mathbb {F}}_2^{n}}^*\). In practice, for functions outside the completed Maiorana-McFarland class, the size of the vertex set becomes relatively small and for instance in dimension \(n=8\) we could verify that typical values for |V| are 0 and 6. We also remark that we consider the graph \(\Gamma \) to be simple as there are no loops (\(D_\textbf{a}D_\textbf{a} f\equiv 0\) holds for all \(\textbf{a}\in {\mathbb {F}}_2^{n}\)); and it is not directed since \(D_\textbf{a}D_\textbf{b}f=D_\textbf{b}D_\textbf{a}f\) for any \(\textbf{a},\textbf{b}\in {\mathbb {F}}_2^{n}\).
$$\begin{aligned} E=\{\{\textbf{a},\textbf{b}\}:\textbf{a},\textbf{b}\in {{\mathbb {F}}_2^{n}}^*; D_\textbf{a}D_\textbf{b} f\equiv 0\}, \end{aligned}$$
From Lemma 2.1, we know that we need to find an (n/2)-dimensional linear subspace V of \({\mathbb {F}}_{2^{n}}\) on which the second-order derivatives of f vanish. From the graph-theoretical perspective, this problem corresponds to finding a clique \(\Lambda \) (complete subgraph) of size \(2^{n/2}-1\) in the graph \(\Gamma \) and additionally checking whether \(V(\Lambda )\cup \{0\}\) forms a linear subspace in \({\mathbb {F}}_{2}^n\). Finding a clique in a graph is known to be an NP-complete problem and, specifically, the time complexity of this search would be of size \({\mathcal {O}}(2^{n2^{n/2}})\). However, in practice, this number is much smaller because the number of vertices (namely |V|) of the graph \(\Gamma \) is almost negligible compared to \(2^n\). The full Sage implementation has been added to the appendix. It might be of interest to optimize further the performance of this algorithm so that larger input sizes can be efficiently tested.
We have considered 100 bent functions in dimension 8 and the average time needed to check whether one function is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) was approximately 17 seconds. For \(n=10\), the average time for checking the property of being in or outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) was 30 minutes. On the other hand, when \(n=12\), the time complexity is approximately 22 h on average. For the purpose of this article, the proposed algorithm is sufficiently efficient and is superior to a straightforward approach of checking all n/2-dimensional subspaces and verifying the vanishing property of the second-order derivatives. Most importantly, all the examples provided in this article (in certain cases the ANFs are also given) can be efficiently checked using the Sage algorithm given in the appendix. We also note the following interesting observation.
Remark 3.1
We remark that the dual of a bent function \(f \in {{{\mathcal {M}}}{{\mathcal {M}}}}\), given by \(f(\textbf{x},\textbf{y})=\textbf{x}\cdot \pi (\textbf{y})\oplus h(\textbf{y})\) for \(\textbf{x},\textbf{y}\in {\mathbb {F}}_2^{n/2}\), where \(\pi \) is a permutation on \({\mathbb {F}}_2^{n/2}\) and h is arbitrary, is apparently in \({{{\mathcal {M}}}{{\mathcal {M}}}}\) (see for instance [7] for the specification of \(f^*\)). The same is true when \(f \in {{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) is considered since the class inclusion is invariant under the EA transform.
3.2 Defining suitable bent 4-decompositions
Recently, a quadruple of distinct bent functions, satisfying that \(f^*_1\oplus f^*_2\oplus f^*_3\oplus f^*_4=1\), was identified in [2]. It was additionally shown that their concatenation \(f_1||f_2||f_3||f_4\) is provably outside the \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) class. More precisely, the authors considered a quadruple of bent functions (not all of them being in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\)) that belong to the \({{\mathcal {C}}}\) and \({{\mathcal {D}}}\) class of Carlet [4] and their suitable “modifications” for this purpose. Nevertheless, the following results show that the same method can generate new bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) when a single bent function (alternatively a pair of bent functions considered in Theorem 3.2) outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) is used.
Theorem 3.1
Let n be even and f be a bent function in n variables. Set \(h(\textbf{x},y_1,y_2)=f(\textbf{x})\oplus y_1y_2\) for \(y_i \in {\mathbb {F}}_2\), so that \(h=f||f||f||(1\oplus f )\in {\mathcal {B}}_{n+2}\) is also bent. Then, f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) if and only if h is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
Proof
It is well-known that \(h=f||f||f||(1\oplus f) \in {\mathcal {B}}_{n+2}\) is bent if f is bent, since \(h(\textbf{x},y_1,y_2)=f(\textbf{x})\oplus y_1y_2\) is the direct sum of two bent functions [12, 23]. Notice that ‘f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) if and only if h is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\)’ is equivalent to ‘f is in \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) if and only if h is in \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\)’.
Suppose first that h is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\), thus we want to show that f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). Assume on the contrary that f is in \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\), thus there exists (at least) one linear subspace \(V \subset {\mathbb {F}}_2^n\) with \(\dim (V)=n/2\) such that \(D_{\textbf{a}'}D_{\textbf{b}'} f\equiv 0\), for any \(\textbf{a}',\textbf{b}'\in V\). Let \(E=V\times \{(0,0),(0,1)\}\) which is a subspace of \({\mathbb {F}}_2^{n+2}\) of dimension \(n/2+1\). We then have thatfor any \(\textbf{a}',\textbf{b}'\in V\) and \((a_1,a_2), (b_1,b_2)\in \{(0,0),(0,1)\}\), thus the second-order derivatives of h vanish on E. Hence, h is in \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) which contradicts our assumption that h is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
$$\begin{aligned} D_{(\textbf{a}', a_1,a_2)}D_{(\textbf{b}',b_1,b_2)} h\equiv 0, \end{aligned}$$
Now, we show that f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) implies that h is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). Assuming \(f \not \in {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\), then for any subspace \(V \subset {\mathbb {F}}_2^n\) with \(\dim (V)=n/2\), we can always find two vectors \(\textbf{a}',\textbf{b}'\) such that \(D_{\textbf{a}'}D_{\textbf{b}'} f\not \equiv 0\). Let \(E \subset {\mathbb {F}}_2^n\times {\mathbb {F}}_2^2\) be any subspace with \(\dim (E)=n/2+1\). There are two cases to be considered.
a.
If \(\dim (E\cap ({\mathbb {F}}_2^n\times \{(0,0)\}))\ge n/2\), then we can find two vectors \((\textbf{a}',0,0), (\textbf{b}',0,0)\) and consequently
$$\begin{aligned} D_{(\textbf{a}',0,0)}D_{(\textbf{b}',0,0)}h=D_{\textbf{a}'}D_{\textbf{b}'} f\not \equiv 0. \end{aligned}$$
b.
If \(\dim (E\cap ({\mathbb {F}}_2^n\times \{(0,0)\}))< n/2\), then we must have \(E\cap (\{\textbf{0}_n\}\times {\mathbb {F}}_2^2)= \{\textbf{0}_n\}\times {\mathbb {F}}_2^2\) since \(\dim (E)=n/2+1\) (using that \(\dim (E\cap ({\mathbb {F}}_2^n\times {\mathbb {F}}_2^2) )=n/2+1\)). Here, there are three cases to be considered.
(a)
If \(D_{\textbf{a}'}D_{\textbf{b}'} f\equiv 0\) for any two vectors \((\textbf{a}',0,0),(\textbf{b}',0,0)\in E\cap ({\mathbb {F}}_2^n\times \{(0,0)\})\), then we can specify \((a_1,a_2)=(1,0),(b_1,b_2)=(1,1)\) so that Thus,
$$\begin{aligned} D_{(a_1,a_2)}D_{(b_1,b_2)}(y_1y_2)=1. \end{aligned}$$
$$\begin{aligned} D_{(\textbf{a}',a_1,a_2)}D_{(\textbf{b}',b_1,b_2)} h=D_{\textbf{a}'}D_{\textbf{b}'} f\oplus D_{(a_1,a_2)}D_{(b_1,b_2)}(y_1y_2)\equiv 1\ne 0. \end{aligned}$$
(b)
If \(D_{\textbf{a}'}D_{\textbf{b}'} f\equiv 1\) for any two nonzero vectors \((\textbf{a}',\textbf{0}_2),(\textbf{b}',\textbf{0}_2)\in E\cap ({\mathbb {F}}_2^n\times \{\textbf{0}_2\})\), then we select \((a_1,a_2)=(1,0),(b_1,b_2)=(0,0)\) so that Thus,
$$\begin{aligned} D_{(a_1,a_2)}D_{(b_1,b_2)} y_1y_2\equiv 0. \end{aligned}$$
$$\begin{aligned} D_{(\textbf{a}',a_1,a_2)}D_{(\textbf{b}',b_1,b_2)} h=D_{\textbf{a}'}D_{\textbf{b}'} f\oplus D_{(a_1,a_2)}D_{(b_1,b_2)}(y_1y_2)\equiv 1\ne 0. \end{aligned}$$
(c)
If \(D_{\textbf{a}'}D_{\textbf{b}'} f\ne const.\) for two nonzero vectors \((\textbf{a}',\textbf{0}_2),(\textbf{b}',\textbf{0}_2)\in E\cap ({\mathbb {F}}_2^n\times \{\textbf{0}_2\})\), then This concludes the proof. \(\square \)
$$\begin{aligned} D_{(\textbf{a}',a_1,a_2)}D_{(\textbf{b}',b_1,b_2)} h=D_{\textbf{a}'}D_{\textbf{b}'} f\ne const. \end{aligned}$$
Corollary 1
Let n and m be even positive integers and h be a bent function in \({\mathcal {B}}_n\). Then, the function \(f(\textbf{x},y_1,y_2,\ldots ,y_m)=h(\textbf{x})\oplus y_1y_2 \oplus {y_3y_4} \oplus \cdots \oplus y_{m-1}y_m\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) if and only if h is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\).
Now, we investigate another non-trivial selection of bent quadruples (different from \(f=f_1||f_1||f_1||(1\oplus f_1)\), which satisfies the necessary and sufficient condition \(f^*_1\oplus f^*_2\oplus f^*_3\oplus f^*_4=1\). It turns out that the basic concatenation method of using just two bent functions, where at least one of them is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\), also generates bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\).
Theorem 3.2
Let \(n=2m\) be even and \(f_1,f_2 \in {\mathcal {B}}_{n}\) be two bent functions. Set \(f=f_1|| f_1||f_2|| (f_2\oplus 1)\), which by (9) givesIf \(f_1\) or \(f_2\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\), then \(f \in {\mathcal {B}}_{n+2}\) is bent and outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
$$\begin{aligned} f(\mathbf {\textbf{x}},y_1,y_2)=(1\oplus y_1)f_1(\mathbf {\textbf{x}})\oplus y_1f_2(\mathbf {\textbf{x}})\oplus y_1y_2,\ \mathbf {\textbf{x}}\in {\mathbb {F}}_2^n,y_1,y_2\in {\mathbb {F}}_2. \end{aligned}$$
(10)
Proof
Since \(f_1^*\oplus f_1^*\oplus f_2^*\oplus (f_2\oplus 1)^*=1\), then f is bent.
For convenience, we denote \(\textbf{a}=(\textbf{a}',a_2,a_3), \textbf{b}=(\textbf{b}',b_2,b_3)\in {\mathbb {F}}_2^{n}\times {\mathbb {F}}_2\times {\mathbb {F}}_2\). Let V be an arbitrary \((m+1)\)-dimensional subspace of \({\mathbb {F}}_2^{n+2}\). From Lemma 2.1, it is sufficient to show that for an arbitrary \((m+1)\)-dimensional subspace V of \({\mathbb {F}}_2^{n+2}\) one can always find two vectors \(\textbf{a},\textbf{b}\in { V}\) such that \( D_{(\textbf{a}', a_2, a_3)}D_{(\textbf{b}', b_2, b_3)}f(\mathbf {\textbf{x}},y_1,y_2)\ne 0 \) for some \((\mathbf {\textbf{x}},y_1,y_2)\in {\mathbb {F}}_2^{n+2}\). We haveThere are two cases to be considered. Thus, there is no \((m+1)\)-dimensional linear subspace of \({\mathbb {F}}_2^{n+2}\) on which the second-order derivatives of f vanish, i.e., f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). \(\square \)
$$\begin{aligned} \begin{array}{rl} D_{(\textbf{a}', a_2, a_3)}D_{(\textbf{b}', b_2, b_3)}f(\mathbf {\textbf{x}},y_1,y_2) =&{} (1\oplus y_1)D_{\textbf{a}'}D_{\textbf{b}'} f_1(\mathbf {\textbf{x}}) \oplus y_1D_{\textbf{a}'}D_{\textbf{b}'} f_2(\mathbf {\textbf{x}}) \\ &{}\oplus a_2 D_{\textbf{b}'} \left( f_1\oplus f_2\right) (\mathbf {\textbf{x}}\oplus \textbf{a}')\oplus b_2D_{\textbf{a}'}\left( f_1\oplus f_2\right) (\mathbf {\textbf{x}}\oplus \textbf{b}')\\ &{} \oplus a_2b_3\oplus a_3b_2. \end{array} \nonumber \\ \end{aligned}$$
(11)
a.
Assuming that \(\dim \left( V\cap ({\mathbb {F}}_2^n\times \{(0,0)\})\right) \ge m\) implies the existence of two vectors \(\textbf{a}=(\textbf{a}',a_2,a_3), \textbf{b}=(\textbf{b}',b_2,b_3)\in V\) such that \( \textbf{a}'\ne \textbf{b}'\), \(a_2=a_3=b_2=b_3=0\), for which \(D_{\textbf{a}'}D_{\textbf{b}'} f_2\not \equiv 0\) if we suppose that \(f_2\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
From (11), for \(y_1=1\), we obtain Thus, we have found \(\textbf{a},\textbf{b}\in V\) such that \(D_{\textbf{a}}D_{\textbf{b}}f(\mathbf {\textbf{x}},1,y_2)\ne 0\), which also implies that \(D_{\textbf{a}}D_{\textbf{b}}f(\mathbf {\textbf{x}},y_1,y_2)\ne 0\).
$$\begin{aligned} D_{(\textbf{a}', a_2, a_3)}D_{(\textbf{b}', b_2, b_3)}f(\mathbf {\textbf{x}},1,y_2)= D_{\textbf{a}'}D_{\textbf{b}'} f_2(\mathbf {\textbf{x}})\not \equiv 0. \end{aligned}$$
Now, assume that \(f_1\notin {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). Similarly, there will exist two vectors \(\textbf{a}=(\textbf{a}'',a_2,a_3), \textbf{b}=(\textbf{b}'',b_2,b_3)\in V\) such that \( \textbf{a}''\ne \textbf{b}''\), \(a_2=a_3=b_2=b_3=0\), for which \(D_{\textbf{a}''}D_{\textbf{b}''} f_1\not \equiv 0\). Setting \(y_1=0\) in (11), we obtain and again we conclude that \(D_{\textbf{a}}D_{\textbf{b}}f(\mathbf {\textbf{x}},y_1,y_2)\ne 0\).
$$\begin{aligned} D_{(\textbf{a}', a_2, a_3)}D_{(\textbf{b}', b_2, b_3)}f(\mathbf {\textbf{x}},0,y_2)=D_{\textbf{a}'}D_{\textbf{b}'} f_1(\mathbf {\textbf{x}})\not \equiv 0, \end{aligned}$$
b.
When \(\dim \left( V\cap ({\mathbb {F}}_2^n\times \{(0,0)\})\right) < {m}\), we have \(V\cap (\{\textbf{0}_n\}\times {\mathbb {F}}_2^2)={\{0_n\} \times }{\mathbb {F}}_2^2\) since \(\dim \left( V\cap ({\mathbb {F}}_2^n\times {\mathbb {F}}_2^2) \right) =m+1\). Furthermore, we can find two vectors \(\textbf{a}=(\textbf{a}',a_2,a_3), \textbf{b}=(\textbf{b}',b_2,b_3)\in V\) such that \( \textbf{a}'=\textbf{0}_n, \textbf{b}'=\textbf{0}_n\), \(a_2=1, b_2=0\), and \(a_3=0, b_3=1\). From (11), we have
$$\begin{aligned} \begin{array}{c} D_{(\textbf{0}_n, 1, 0)}D_{(\textbf{0}_n, 0, 1)}f(\mathbf {\textbf{x}},y_1,y_2) = 1\ne 0. \end{array} \end{aligned}$$
(12)
Example 3.1
Let \(f_1,f_2\in {\mathcal {B}}_8\) be defined by \(f_1(\mathbf {\textbf{x}},\mathbf {\textbf{y}})=\textbf{x}\cdot \mathbf {\textbf{y}}\) and \(f_2(\mathbf {\textbf{x}},\mathbf {\textbf{y}})=\mathbf {\textbf{x}}\cdot \pi _2(\mathbf {\textbf{y}})\oplus \delta _0(\mathbf {\textbf{x}})\), respectively, where \(\pi _2=(0, 1, 2, 3, 4, 5, 8, 10, 6, 12, 7, 15, 13, 11, 9, 14)\) is a permutation of \({\mathbb {F}}_2^{4}\) in integer form and \(\mathbf {\textbf{x}},\mathbf {\textbf{y}}\in {\mathbb {F}}_2^{4}\). Here, \(\delta _0(\mathbf {\textbf{x}})=\prod _{i=1}^4(1\oplus x_i)\) is the indicator of \(\{{\textbf{0}}_4\)}. We note that \(f_1\in {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) and \(f_2\in {{\mathcal {D}}}_0 \setminus {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\), where \({{\mathcal {D}}}_0\) is the class of bent functions introduced by Carlet [4] whose members are of the same form as \(f_2\) above. Let \({\mathfrak {f}}_1=(f_1,f_1,f_2,f_2\oplus 1)\) and \( {\mathfrak {f}}_2=(f_2,f_2,f_1,f_1\oplus 1)\) be defined via (10). Using the algorithm in Sect. 3.1, we have confirmed that \({\mathfrak {f}}_1,{\mathfrak {f}}_2\in {\mathcal {B}}_{10}\) are both bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
An iterative design of bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) follows easily from Theorem 3.2.
Corollary 2
Let \(f_1,f_2\in {\mathcal {B}}_n\) be two bent functions such that \(f_1\) or \(f_2\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). Set \({\mathfrak {f}}_1^{(1)}=(f_1,f_1,f_2,f_2\oplus 1)\) and \({\mathfrak {f}}_2^{(1)}=(f_2,f_2,f_1,f_1\oplus 1)\). For \(k\ge 2\) we defineandThen, \({\mathfrak {f}}_1^{(k)}\) and \({\mathfrak {f}}_2^{(k)}\) are bent functions in \(n+2k\) variables outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
$$\begin{aligned} {\mathfrak {f}}_1^{(k)}=({\mathfrak {f}}_1^{(k-1)},{\mathfrak {f}}_1^{(k-1)},{\mathfrak {f}}_2^{(k-1)},{\mathfrak {f}}_2^{(k-1)}\oplus 1) \end{aligned}$$
$$\begin{aligned} {\mathfrak {f}}_2^{(k)}=({\mathfrak {f}}_2^{(k-1)},{\mathfrak {f}}_2^{(k-1)},{\mathfrak {f}}_1^{(k-1)},{\mathfrak {f}}_1^{(k-1)}\oplus 1). \end{aligned}$$
3.3 Semi-bent case of 4-decomposition
The construction of disjoint spectra semi-bent functions was treated in several articles, see [15] and references therein. In terms of the spectral design method in [15], constructing quadruples of semi-bent functions \((f_1,f_2,f_3,f_4)\) on \({\mathbb {F}}_2^n\) (with n even), whose Walsh spectral values belong to \(\{0,\pm 2^{\frac{n+2}{2}}\}\), with pairwise disjoint spectra ( so that \(f_i\) and \(f_j\) are disjoint spectra functions for \(1 \le i \ne j \le 4\)) can be easily achieved by specifying suitable Walsh supports. It has already been observed in [16, 29] that trivial plateaued functions, having an affine subspace as their Walsh support, essentially correspond to partially bent functions introduced by Carlet in [5] which admit linear structures. Nevertheless, the selection of these Walsh supports as affine subspaces or subsets will be shown to be irrelevant for the class inclusion of the resulting bent functions, which will be entirely governed by the bent duals.
3.3.1 Known results on the design methods of plateaued Boolean functions
Before proving the main results of this section, we will give a brief overview of some known useful results obtained in [15] regarding the construction and properties of s-plateaued Boolean functions. For simplicity, we adopt these results for semi-bent functions, thus \(s=2\), and employ only the parts relevant for our purposes.
Theorem 3.3
[15, Theorem 3.3 (with \(s=2\))] Let \(S_f=\textbf{v}\oplus EM=\{{\varvec{\omega }}_0,\ldots ,{\varvec{\omega }}_{2^{n-2}-1}\} \subset {{\mathbb {F}}}_{2}^n\), for some \(\textbf{v} \in {\mathbb {F}}^n_2\), \(M\in GL(n,{\mathbb {F}}_2)\) and lexicographically ordered subset \(E=\{\textbf{e}_0,\textbf{e}_1, \ldots , \textbf{e}_{2^{n-2}-1}\}\subset {\mathbb {F}}^n_2\), where n is even. For a function \(g:{{\mathbb {F}}}_{2}^{n-2}\rightarrow {\mathbb {F}}_2\) such that \(wt(g)=2^{n-3}+ 2^{\frac{n-2}{2}-1}\) or \(wt(g)=2^{n-3}-2^{\frac{n-2}{2}-1}\) (having bent weight), let the Walsh spectrum of f on \({\mathbb {F}}_2^n\) be defined (by identifying \(\textbf{x}_i \in {{\mathbb {F}}}_{2}^{n-2}\) and \({\varvec{\omega }}_i \in S_f\) through \(\textbf{e}_i \in E\) using (5)) asThen:
$$\begin{aligned} W_f(\mathbf {\mathbf {\textbf{u}}})= \left\{ \begin{array}{ll} 2^{\frac{n+2}{2}}(-1)^{g(\textbf{x}_i)}, &{} \text { for } \mathbf {\mathbf {\textbf{u}}}= \textbf{v} \oplus \textbf{e}_iM \in S_f,\\ 0, &{} \mathbf {\mathbf {\textbf{u}}} \not \in S_f. \\ \end{array} \right. \end{aligned}$$
(13)
(i)
f is an 2-plateaued (semi-bent) function if and only if g is at bent distance to where for a subset \(B\subset {\mathcal {B}}_{n}\) a function g is said to be at bent distance to B if for all \(f\in B\) it holds that \(d_H(f,g)=2^{n-1}\pm 2^{n/2-1}\).
$$\begin{aligned} \Phi _{f}= & {} \{\phi _\mathbf {\mathbf {\textbf{u}}}:{\mathbb {F}}^{n-2}_2\rightarrow {\mathbb {F}}_2:\; \nonumber \\{} & {} \chi _{\phi _\mathbf {\mathbf {\textbf{u}}}}=((-1)^{\mathbf {\mathbf {\textbf{u}}}\cdot \omega _{0}},(-1)^{\mathbf {\mathbf {\textbf{u}}}\cdot \omega _{1}},\ldots ,(-1)^{\mathbf {\mathbf {\textbf{u}}}\cdot \omega _{2^{n-2}-1}}),\;\omega _i\in S_f,\; \mathbf {\mathbf {\textbf{u}}}\in {\mathbb {F}}^{n}_2\}, \end{aligned}$$
(14)
(ii)
If \(E\subset {\mathbb {F}}^n_2\) is a linear subspace, then f is semi-bent if and only if g is a bent function on \({\mathbb {F}}^{n-2}_2\).
Remark 3.2
Since \(|S_f|=2^{n-2}\) and the absolute value of the Walsh coefficients in Theorem 3.3 is \(2^{\frac{n+2}{2}}\), Parseval’s identity \(\sum _{\textbf{u} \in {\mathbb {F}}_2^n} W_f(\textbf{u})^2=2^{2n}\) is clearly satisfied. For ease of notation, we will consider \(f \in {\mathcal {B}}_{n+2}\) and use a dual bent function \(g \in {\mathcal {B}}_n\), which essentially corresponds to the dual function \({\overline{f}}^*\) discussed in Sect. 2.1 and specified in (5). The Walsh support \(S_f \subset {\mathbb {F}}_2^{n+2}\) with \(|S_f|=2^n\), can be specified as a binary matrix of size \(2^n \times (n+2)\) of the form \(S_f=(\textbf{c}\oplus {\mathbb {F}}_2^nM)\wr T_{\mu _1}\wr T_{\mu _2},\) \(M\in GL(n,{\mathbb {F}}_2)\) and \(\textbf{c}\in {\mathbb {F}}^{n}_2\). Here, the part \(\textbf{c}\oplus {\mathbb {F}}_2^nM\) is an affine permutation of \({\mathbb {F}}_2^n\) and corresponds to the first n columns of \(S_f\); whereas the last two columns \(T_{\mu _1}\wr T_{\mu _2}\) of \(S_f\) are binary truth tables of \(\mu _1,\mu _2 \in {\mathcal {B}}_n\).
To construct nontrivial semi-bent functions (whose Walsh supports are subsets), one can employ bent functions in the \({{\mathcal {M}}}{{\mathcal {M}}}\) class defined bywhere \(\psi \) is an arbitrary permutation on \({\mathbb {F}}^{n/2}_2\) and \(t \in {\mathcal {B}}_{n/2}\) is arbitrary. We give below a slightly modified version of Theorem 4.2 in [15], since we are interested in semi-bent functions in even dimensions. Therefore, we define the Walsh support as \(S_f=(\textbf{c}\oplus EM)\wr T_{\mu }\wr T_{\mu }\) rather than \(S_f=(\textbf{c}\oplus EM)\wr T_{\mu }\) as originally in [15]. Notice that the use of a nonlinear function \(\mu : {\mathbb {F}}_2^n \rightarrow {\mathbb {F}}_2\) ensures that \(S_f\) is not an affine/linear subspace.
$$\begin{aligned} g(\textbf{x},\textbf{y})=\textbf{x}\cdot \psi (\textbf{y})\oplus t(\textbf{y}); \;\;\textbf{x},\textbf{y}\in {\mathbb {F}}^{n/2}_2, \end{aligned}$$
(15)
Theorem 3.4
[15, Theorem 4.2] Let \(g(\textbf{x},\textbf{y})=\textbf{x}\cdot \psi (\textbf{y})\), \(\textbf{x},\textbf{y}\in {\mathbb {F}}^{n/2}_2\), be a bent function, n is even. For an arbitrary matrix \(M\in GL(n,{\mathbb {F}}_2)\) and vector \(\textbf{c}\in {\mathbb {F}}^{n}_2\), let \(S_f=(\textbf{c}\oplus EM)\wr T_{\mu }\wr T_{\mu },\) where \(E={\mathbb {F}}^{n}_2\) is ordered lexicographically and \(\mu \in {\mathcal {B}}_{n}\). We have:
(i)
Let \(E_1,E_2\) be subspaces of \( {\mathbb {F}}^{n/2}_2\) such that \(\psi (E_2)=E^{\perp }_1\) and define \(\mu (\textbf{x},\textbf{y})=\phi _{E_1}(\textbf{x})\phi _{E_2}(\textbf{y})\), where \(\phi _{E_i}\) denotes the characteristic function of \(E_i\). Then, \(f:{\mathbb {F}}^{n+2}_2\rightarrow {\mathbb {F}}_2\), whose Walsh spectrum is specified by means of (13) in Theorem 3.3 (with dimension \(n+2\) instead of n), is a semi-bent function.
(ii)
Let L be a subspace of \( {\mathbb {F}}^{n}_2\) and define \(\mu (\textbf{x},\textbf{y})=\phi _L(\textbf{x})\). If \(\psi ^{-1}(\textbf{v}+L^{\perp })\) is an affine subspace for all \(\textbf{v}\in {\mathbb {F}}^{n}_2\), then \(f:{\mathbb {F}}^{n+2}_2\rightarrow {\mathbb {F}}_2\), whose Walsh spectrum is specified by means of (13) in Theorem 3.3 (with dimension \(n+2\) instead of n), is a semi-bent function.
3.3.2 Bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) using semi-bent functions with suitable duals
By employing the above results, the authors in [15] also proposed a construction method of disjoint spectra plateaued functions, see Theorem 4.4 in [15], and additionally showed that these functions can be efficiently utilized for the construction of bent functions. For the particular case of specifying four semi-bent functions on \({\mathbb {F}}_2^{n+2}\), by using a bent dual \(g \in {\mathcal {B}}_n\), it is convenient to express \({\mathbb {F}}_2^{n+2}=V \oplus Q\) where for simplicity \(V={\mathbb {F}}_2^{n} \times \{(0,0)\}\) and \(Q=\textbf{0}_n \times {\mathbb {F}}_2^2\). Notice that the choice of V leads to the canonical concatenation/decomposition given by (9). The main idea is then to specify disjoint Walsh supports of semi-bent functions \(f_i\) on the cosets of V in \({\mathbb {F}}_2^{n+2}\). The reason for selecting \(S_f(\textbf{c}\oplus {\mathbb {F}}_2^{n}M)\wr T_{t_1}\wr T_{t_2} \) in Theorem 3.5 as a non-affine subspace is to demonstrate a somewhat harder design rationale that employs Theorem 3.3(i), which requires that the set \(\Phi _f\) is at bent distance to the bent dual g. Again, the use of a suitable bent dual \(g \in {\mathcal {B}}_n\) (taken outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\)) is decisive when the design of bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) is considered.
We note the following notion of the so-called relaxed linearity index introduced in [22].
Definition 3.1
[22] A vector subspace \(U \subseteq {\mathbb {F}}_2^n\) is called a relaxed \({{{\mathcal {M}}}{{\mathcal {M}}}}\)-subspace of a Boolean function \(f\in {\mathcal {B}}_n\), if for all \(\textbf{a}, \textbf{b} \in U\) the second-order derivatives \(D_{\textbf{a}}D_\textbf{b}f\) are either constant zero or constant one functions, that is, \(D_{\textbf{a}}D_\textbf{b}f=0\) or \(D_{\textbf{a}}D_\textbf{b}f=1\). We denote by \(\mathcal {RMS}_r(f)\) the collection of all r-dimensional relaxed \({{{\mathcal {M}}}{{\mathcal {M}}}}\)-subspaces of a Boolean function f and by \(\mathcal {RMS}(f)\) the collectionFor a Boolean function \(f\in {\mathcal {B}}_n\) its relaxed linearity indexr-ind(f) is defined by
$$\begin{aligned} \mathcal {RMS}(f):=\bigcup \limits _{r=1}^{n}\mathcal {RMS}_r(f). \end{aligned}$$
$$\begin{aligned} r-\text {ind}(f):=\max \limits _{U\in \mathcal {RMS}(f) }\dim (U). \end{aligned}$$
Theorem 3.5
Let \(g\notin {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) be a bent function in n variables, n even, with r-ind\((g)<n/2-2\). For an arbitrary matrix \(M\in GL(n,{\mathbb {F}}_2^{})\) and vector \(\textbf{c}\in {\mathbb {F}}_2^{n}\), let \(S_f=(\textbf{c}\oplus {\mathbb {F}}_2^{n}M)\wr T_{t_1}\wr T_{t_2} \subset {\mathbb {F}}_2^{n+2}\), where \(t_1,t_2\in {\mathcal {B}}_{n}\) such that \(g(\textbf{x},\textbf{y})\oplus v_1t_1(\textbf{x},\textbf{y})\oplus v_2t_2(\textbf{x},\textbf{y})\) is bent for any \( v_1,v_2\in {\mathbb {F}}_2^{}\), where \( \textbf{x},\textbf{y}\in {\mathbb {F}}_2^{n/2}\). Let \(Q=\{{\textbf{0}}_n\}\times {\mathbb {F}}_2^{2}= \{\textbf{q}_{00},\textbf{q}_{01},\textbf{q}_{10},\textbf{q}_{11}\}\) and set \(S_{f_{\textbf{a}}}=\textbf{q}_{\textbf{a}} \oplus S_f\), for \(\textbf{q}_{\textbf{a}} \in Q\) and \(\textbf{a}\in {\mathbb {F}}_2^{2}\). Then, the functions \(f_{\textbf{a}} \in {\mathcal {B}}_{n+2}\), constructed using Theorem 3.3 with \(S_{f_{\textbf{a}}}\) and g, are semi-bent functions on \({\mathbb {F}}_2^{n+2}\) with pairwise disjoint spectra. Moreover, the function \({\mathfrak {f}}\in {\mathcal {B}}_{n+4}\), whose canonical restrictions are \({\mathfrak {f}}|_{{\mathbb {F}}_2^{n+2}\times \{\textbf{a}\}}:=f_{\textbf{a}}\), where \(\textbf{a}\in {\mathbb {F}}_2^{2}\) (thus \({\mathfrak {f}}=f_{00}||f_{01}||f_{10}||f_{11}\)), is a bent function outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
Proof
Let \(\textbf{c}\in {\mathbb {F}}_2^{n}\) and \(M\in GL(n,{\mathbb {F}}_2^{})\) be arbitrary. Let \(S_f=(\textbf{c}\oplus {\mathbb {F}}_2^{n} M)\wr T_{t_1}\wr T_{t_2}\), where \(t_1,t_2\in {\mathcal {B}}_{n}\). The columns of \(\textbf{c}\oplus {\mathbb {F}}_2^{n}M\) correspond to affine functions in n variables, say \(l_1,\ldots ,l_n \in {\mathcal {A}}_n\). Thus, by assumption on g, the function \(g\oplus \textbf{v}\cdot (l_1,\ldots ,l_n,t_1,t_2)\) is bent for any \(\textbf{v}\in {\mathbb {F}}_2^{n+2}\). Hence, g is at bent distance to \(\Phi _f=\{\phi _\mathbf {\mathbf {\textbf{v}}}\in {\mathcal {B}}_{n}:T_{\phi _\mathbf {\mathbf {\textbf{v}}}}=(\mathbf {\mathbf {\textbf{v}}}\cdot \omega _0,\ldots ,\mathbf {\mathbf {\textbf{v}}}\cdot \omega _{2^n-1}),\ \omega _i\in S_f,\ \mathbf {\mathbf {\textbf{v}}}\in {\mathbb {F}}_2^{n+2}\}\). Let \(S_{f_{\textbf{a}}}=\textbf{q}_{\textbf{a}} \oplus S_f\), for \(\textbf{q}_{\textbf{a}} \in Q\). By Theorem 3.3(i), the functions \(f_{\textbf{a}}\in {\mathcal {B}}_{n+2}\), whose Walsh spectral values at \(\textbf{v} \in {\mathbb {F}}_2^{n+2}\) are defined by:are 2-plateaued (semi-bent) functions, for \(\textbf{a}\in {\mathbb {F}}_2^{2}\). Furthermore, we have \(\cup _{\mathbf {q_{\textbf{a}}}\in Q}(\textbf{q}_{\textbf{a}}\oplus S_f)={\mathbb {F}}_2^{n+2}\) and the function \({\mathfrak {f}}=f_{00}||f_{01}||f_{10}||f_{11} \in {\mathcal {B}}_{n+4}\) is bent by Theorem 2.2(ii), since the restrictions \(f_{\mathbf {\textbf{a}}}\) are pairwise disjoint spectra semi-bent functions.
$$\begin{aligned} W_{f_{\textbf{a}}}(\mathbf {\mathbf {\textbf{v}}})=\left\{ \begin{array}{ll} 2^{\frac{n+4}{2}}(-1)^{g(\textbf{x}_i,\textbf{y}_i)},&{}\ \mathbf {\mathbf {\textbf{v}}}=(\textbf{c}\oplus (\textbf{x}_i,\textbf{y}_i)\cdot M,t_1(\textbf{x}_i,\textbf{y}_i),t_2(\textbf{x}_i,\textbf{y}_i))\oplus \textbf{q}_{\textbf{a}} \in S_{f_{\textbf{a}}}\\ 0,&{}\ \mathbf {\mathbf {\textbf{v}}}\notin S_{f_{\textbf{a}}} \end{array}\right. , \nonumber \\ \end{aligned}$$
(16)
It remains to show that \({\mathfrak {f}}\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). For convenience, we write \(\mathbf {\mathbf {\textbf{u}}}=({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }},{\varvec{\omega }})\in {\mathbb {F}}_2^{n/2}\times {\mathbb {F}}_2^{n/2}\times {\mathbb {F}}_2^{2}\times {\mathbb {F}}_2^{2}\). Then, the Walsh-Hadamard transform of \({\mathfrak {f}}\) at \(\mathbf {\mathbf {\textbf{u}}} \in {\mathbb {F}}_2^{n+ 4}\) evaluates to:As \(\cup _{\textbf{q}\in Q}(\textbf{q}\oplus S_f)={\mathbb {F}}_2^{n+2}\) and \(\textbf{q}\oplus S_f\cap \textbf{q}'\oplus S_f=\emptyset \) for \(\textbf{q}\ne \textbf{q}'\), we have that \(({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})\) is in exactly one support \(S_{f_{\textbf{w}}}\) for some \(\textbf{w}\in {\mathbb {F}}_2^{2}\). We note that \(({\varvec{\alpha }},{\varvec{\beta }})=\textbf{c}\oplus ({\varvec{\alpha }}',{\varvec{\beta }}')\cdot M\) for some \(({\varvec{\alpha }}',{\varvec{\beta }}')\in {\mathbb {F}}_2^{n/2}\times {\mathbb {F}}_2^{n/2}\) and \(\varvec{\gamma }=(t_1({\varvec{\alpha }}',{\varvec{\beta }}'),t_2({\varvec{\alpha }}',{\varvec{\beta }}'))\oplus \textbf{a}_{\varvec{\gamma }}\) for some \(\textbf{a}_{\varvec{\gamma }}\in {\mathbb {F}}_2^{2}\), whose choice depends on the value of \(\varvec{\gamma }\). Hence,Thus, we have thatwhich implies that the dual \({\mathfrak {f}}^*\in {\mathcal {B}}_{n+4}\) of \({\mathfrak {f}}\) is defined byfor \(\textbf{x},\textbf{y}\in {\mathbb {F}}_2^{n/2}\) and \(\textbf{z},\textbf{w}\in {\mathbb {F}}_2^{2}\). Without loss of generality, let us consider the functionwhereWe note that \({\mathfrak {h}}\) and \({\mathfrak {f}}^*\) are EA-equivalent functions and thus belong to the same completed class of bent functions.
$$\begin{aligned} W_{{\mathfrak {f}}}(\mathbf {\mathbf {\textbf{u}}})&=\sum _{(\textbf{x},\textbf{y},\textbf{z},\textbf{w})\in ({\mathbb {F}}_2^{n/2})^2\times ({\mathbb {F}}_2^{2})^2}(-1)^{{\mathfrak {f}}(\textbf{x},\textbf{y},\textbf{z},\textbf{w})\oplus (\textbf{x},\textbf{y},\textbf{z},\textbf{w})\cdot \mathbf {\mathbf {\textbf{u}}}}\\&=\sum _{\textbf{w}\in {\mathbb {F}}_2^{2}}\sum _{(\textbf{x},\textbf{y},\textbf{z})\in ({\mathbb {F}}_2^{n/2})^2\times {\mathbb {F}}_2^{2}}(-1)^{f_{\textbf{w}}(\textbf{x},\textbf{y},\textbf{z})\oplus (\textbf{x},\textbf{y},\textbf{z})\cdot ({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})\oplus \textbf{w}\cdot \varvec{\omega }}\\&=\sum _{\textbf{w}\in {\mathbb {F}}_2^{2}}(-1)^{\textbf{w}\cdot \varvec{\omega }}\sum _{(\textbf{x},\textbf{y},\textbf{z})\in ({\mathbb {F}}_2^{n/2})^2\times {\mathbb {F}}_2^{2}}(-1)^{f_{\textbf{w}}(\textbf{x},\textbf{y},\textbf{z})\oplus (\textbf{x},\textbf{y},\textbf{z})\cdot ({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})}\\&=\sum _{\textbf{w}\in {\mathbb {F}}_2^{2}}(-1)^{\textbf{w}\cdot \varvec{\omega }}W_{f_{\textbf{w}}}({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})=(*). \end{aligned}$$
$$\begin{aligned} ({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})=(\textbf{c}\oplus ({\varvec{\alpha }}',{\varvec{\beta }}')\cdot M,t_1({\varvec{\alpha }}',{\varvec{\beta }}'),t_2({\varvec{\alpha }}',{\varvec{\beta }}'))\oplus \textbf{q}_{\textbf{a}_{\gamma }}. \end{aligned}$$
$$\begin{aligned} (*)&=2^{\frac{n+4}{2}}\cdot (-1)^{\textbf{a}_{\gamma }\cdot \varvec{\omega }\oplus g({\varvec{\alpha }}',{\varvec{\beta }}')}\\&=2^{\frac{n+4}{2}}\cdot (-1)^{((t_1((({\varvec{\alpha }},{\varvec{\beta }})\oplus \textbf{c})\cdot M^{-1}),t_2((({\varvec{\alpha }},{\varvec{\beta }})\oplus \textbf{c})\cdot M^{-1}))\oplus \varvec{\gamma })\cdot \varvec{\omega }\oplus g((({\varvec{\alpha }},{\varvec{\beta }})\oplus \textbf{c})\cdot M^{-1})} \end{aligned}$$
$$\begin{aligned}{} & {} {\mathfrak {f}}^*({\textbf{x}},{\textbf{y}},{\textbf{z}},{\textbf{w}})=((t_1((({\textbf{x}},{\textbf{y}})\oplus \textbf{c})\cdot M^{-1}),t_2((({\textbf{x}},{\textbf{y}})\oplus \textbf{c})\cdot M^{-1}))\oplus \textbf{z})\\{} & {} \cdot \textbf{w}\oplus g((({\textbf{x}},{\textbf{y}})\oplus \textbf{c})\cdot M^{-1}), \end{aligned}$$
$$\begin{aligned} {\mathfrak {h}}({\textbf{x}},{\textbf{y}},{\textbf{z}},{\textbf{w}})&={\mathfrak {f}}^*(({\textbf{x}},{\textbf{y}},{\textbf{z}},{\textbf{w}})\cdot M'\oplus (\textbf{c},\textbf{0}_2,\textbf{0}_2))\\&=((t_1(\textbf{x},\textbf{y}),t_2(\textbf{x},\textbf{y}))\oplus \textbf{z})\cdot \textbf{w}\oplus g({\textbf{x}},{\textbf{y}})\\&=g({\textbf{x}},{\textbf{y}})\oplus \textbf{z}\cdot \textbf{w}\oplus (t_1(\textbf{x},\textbf{y}),t_2(\textbf{x},\textbf{y}))\cdot \textbf{w}, \end{aligned}$$
$$\begin{aligned} M' = \left( \begin{array}{c|c} M &{} O_4 \\ \hline O_4 &{} I_4 \\ \end{array}\right) . \end{aligned}$$
Let us now consider the second-order derivative of \({\mathfrak {h}}\). Suppose that V is some \((n+4)/2\)-dimensional subspace of \({\mathbb {F}}_2^{n+4}={\mathbb {F}}_2^{n/2} \times {\mathbb {F}}_2^{n/2} \times {\mathbb {F}}_2^2 \times {\mathbb {F}}_2^2\) and let \(\alpha =(\alpha ^{(1)},\alpha ^{(2)},\alpha ^{(3)},\alpha ^{(4)}),\beta =(\beta ^{(1)},\beta ^{(2)},\beta ^{(3)},\beta ^{(4)})\in V\), where \(\alpha ^{(1)},\alpha ^{(2)},\beta ^{(1)},\beta ^{(2)}\in {\mathbb {F}}_2^{n/2},\alpha ^{(3)},\alpha ^{(4)},\beta ^{(3)},\beta ^{(4)}\in {\mathbb {F}}_2^{2}\). For easier notation, we will denote with \(\alpha _{12}=(\alpha ^{(1)},\alpha ^{(2)})\) and \(\beta _{12}=(\beta ^{(1)},\beta ^{(2)})\). The second-order derivative of \({\mathfrak {h}}\) evaluates toFirst, we note that there are no bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) for \(n\le 6\), i.e., we must have \(n\ge 8\). Hence, the smallest possible dimension we can consider is \(8+4=12\) for which the vanishing subspace V has dimension 6. Since \(\dim (V)= n/2+2\), we haveHence, without loss of generality, we can take \(\alpha =(\alpha ^{(1)},\alpha ^{(2)},\alpha ^{(3)},0,0)\) and \(\beta =(\beta ^{(1)},\beta ^{(2)},\beta ^{(3)},0,0)\) for some distinct nonzero \(\alpha _{12},\beta _{12}\). From (17), for \({\textbf{w}}=0_2\) and \(\alpha ^{(4)}=\beta ^{(4)}=(0,0)\), we have thatFurthermore, since \(\dim (\{(\textbf{x},\textbf{y})\in {\mathbb {F}}_2^{n/2}\times {\mathbb {F}}_2^{n/2}:(\textbf{x},\textbf{y},\textbf{z},\textbf{w})\in V\})\ge n/2-2\) and r-ind\((g)<n/2-2\) we have thatThus \({\mathfrak {h}}\notin {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\), which implies that \({\mathfrak {f}}^*\notin {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). By Remark 3.1, it means that \({\mathfrak {f}}\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). \(\square \)
$$\begin{aligned} D_{\alpha }D_{\beta }{\mathfrak {h}}(\textbf{x},\textbf{y},\textbf{z},\textbf{w})= & {} D_{\alpha _{12}}D_{\beta _{12}}g(\textbf{x},\textbf{y})\oplus \textbf{w}\cdot (D_{\alpha _{12}}D_{\beta _{12}}t_1(\textbf{x},\textbf{y}), D_{\alpha _{12}}D_{\beta _{12}}t_2(\textbf{x},\textbf{y})) \nonumber \\{} & {} \oplus \alpha ^{(4)}\cdot (D_{\beta _{12}}t_1((\textbf{x},\textbf{y})\oplus \alpha _{12}),D_{\beta _{12}}t_2((\textbf{x},\textbf{y})\oplus \alpha _{12})) \nonumber \\{} & {} \oplus \beta ^{(4)}\cdot (D_{\alpha _{12}}t_1((\textbf{x},\textbf{y})\oplus \beta _{12}),D_{\alpha _{12}}t_2((\textbf{x},\textbf{y})\oplus \beta _{12})) \nonumber \\{} & {} \oplus \alpha ^{(3)}\cdot \beta ^{(3)} \oplus \alpha ^{(4)}\cdot \beta ^{(4)}. \end{aligned}$$
(17)
$$\begin{aligned} \dim (\{(\textbf{x},\textbf{y},\textbf{z},0_2)\in {\mathbb {F}}_2^{n/2}\times {\mathbb {F}}_2^{n/2}\times {\mathbb {F}}_2^{2}:(\textbf{x},\textbf{y},\textbf{z},\textbf{w})\in V\})\ge n/2. \end{aligned}$$
$$\begin{aligned} D_{\alpha }D_{\beta }{\mathfrak {h}}(\textbf{x},\textbf{y},\textbf{z},\textbf{w})\Big |_{{\textbf{w}}=0_2}=D_{\alpha _{12}}D_{\beta _{12}}g(\textbf{x},\textbf{y})\oplus \alpha ^{(3)}\cdot \beta ^{(3)}. \end{aligned}$$
$$\begin{aligned} D_{\alpha }D_{\beta }{\mathfrak {h}}(\textbf{x},\textbf{y},\textbf{z},\textbf{w})|_{\textbf{w}=0_2}\ne 0. \end{aligned}$$
Remark 3.3
The condition that r-ind\((g)< n/2-2\) is quite strict and can be relaxed in certain cases. For instance, taking that \(t_1=t_2=0\) in Theorem 3.5, the function \( {\mathfrak {h}}({\textbf{x}},{\textbf{y}},{\textbf{z}},{\textbf{w}})=g({\textbf{x}},{\textbf{y}})\oplus \textbf{z}\cdot \textbf{w}\oplus (t_1(\textbf{x},\textbf{y}),t_2(\textbf{x},\textbf{y}))\cdot \textbf{w}\) becomes \( {\mathfrak {h}}({\textbf{x}},{\textbf{y}},{\textbf{z}},{\textbf{w}})=g({\textbf{x}},{\textbf{y}})\oplus \textbf{z}\cdot \textbf{w}\), which by Corollary 1 is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) if and only if g is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). This also indicates that the choice of a non-affine Walsh support is not decisive for the class inclusion since the support \(S_f\) in Theorem 3.5 is affine when \(t_1=t_2=0\).
Since \(g \in {\mathcal {B}}_n\) is supposed to be a bent function outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) (with additional restriction that r-ind\((g) <n/2-2\)), we can employ the class \({{\mathcal {D}}}_0\) of Carlet [4] or certain families of bent functions in \( {{\mathcal {C}}}\) and \({{\mathcal {D}}}\) that are provably outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) [18, 26, 28]. Alternatively g can be taken from the recent classes \( {{\mathcal {S}}}{{\mathcal {C}}}\) and \({{\mathcal {C}}}{{\mathcal {D}}}\) [1, 2], which are specified in Corollary 3 below. Notice that the subspaces \(L, E_1, E_2\) used to define g in Corollary 3 below, satisfy certain conditions with respect to the permutation \(\pi \), see [4, 26, 28]. However, there exist efficient design methods for specifying bent functions in the above classes that are provably outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) [1, 2, 18, 26, 28]. On the other hand, for \(t_1,t_2 \in {\mathcal {B}}_n\) we use certain indicators that preserve the bentness of \(g(\textbf{x},\textbf{y})\oplus v_1t_1(\textbf{x},\textbf{y})\oplus v_2t_2(\textbf{x},\textbf{y})\). The results are summarised in the following corollary, where we denote \(\delta _0(\textbf{x})=\prod _{i=1}^{n/2}(x_i \oplus 1)\) which is the indicator function of \(\{0_{n/2}\} \times {\mathbb {F}}_2^{n/2}\). Notice again that taking \(t_1=t_2=0\) in Corollary 3, it is sufficient to take any bent function g outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\).
Corollary 3
With the same notation as in Theorem 3.5, if a bent function \(g\in {\mathcal {B}}_n\) satisfies r-ind\((g)< n/2-2\) and \(t_1,t_2\in {\mathcal {B}}_{n}\) are defined by: then \({\mathfrak {f}}\in {\mathcal {B}}_{n+4}\) is a bent function outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
(i)
\(g(\textbf{x},\textbf{y})=\textbf{x}\cdot \pi (\textbf{y})\oplus \delta _0(\textbf{x})\in {{\mathcal {D}}}_0\setminus {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#},\ t_1(\textbf{x},\textbf{y})=t_2(\textbf{x},\textbf{y})=\delta _0(\textbf{x}),\ \textbf{x},\textbf{y}\in {\mathbb {F}}_2^{n/2}\),
(ii)
\(g(\textbf{x},\textbf{y})=\textbf{x}\cdot \pi (\textbf{y})\oplus {\textbf{1}}_{L^{\perp }}(\textbf{x})\in {{\mathcal {C}}}\setminus {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#},\ t_1,t_2\) correspond to \({\textbf{1}}_{L^{\perp }}(\textbf{x})\) or \(\delta _0(\textbf{x}),\ \textbf{x},\textbf{y}\in {\mathbb {F}}_2^{n/2}\),
(iii)
\(g(\textbf{x},\textbf{y})=\textbf{x}\cdot \pi (\textbf{y})\oplus {\textbf{1}}_{L^{\perp }}(\textbf{x})\oplus \delta _0(\textbf{x})\in {{\mathcal {S}}}{{\mathcal {C}}}\setminus {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#},\ t_1,t_2\) correspond to \({\textbf{1}}_{L^{\perp }}(\textbf{x})\) or \(\delta _0(\textbf{x}),\ \textbf{x},\textbf{y}\in {\mathbb {F}}_2^{n/2}\), or
(iv)
\(g(\textbf{x},\textbf{y})=\textbf{x}\cdot \pi (\textbf{y})\oplus {\textbf{1}}_{L^{\perp }}(\textbf{x})\oplus {\textbf{1}}_{E_1}(\textbf{x}){\textbf{1}}_{E_2}(\textbf{y})\in {{\mathcal {C}}}{{\mathcal {D}}}\setminus {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#},\ t_1(\textbf{x},\textbf{y})=t_2(\textbf{x},\textbf{y})={\textbf{1}}_{L^{\perp }}(\textbf{x}),\ \textbf{x},\textbf{y}\in {\mathbb {F}}_2^{n/2}\),
In the following example, we take \(g\in {{\mathcal {D}}}_0\setminus {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) in 8 variables (satisfying the condition r-ind\((g)<8/2-2=2\)) to construct a bent function in 12 variables outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) by means of Theorem 3.5. The result was also confirmed using our algorithm in Sect. 3.1.
Example 3.2
Let \(g(\textbf{x},\textbf{y})=\textbf{x}\cdot \pi (\textbf{y})\oplus \delta _0(\textbf{x}),\ \textbf{x},\textbf{y}\in {\mathbb {F}}_2^{4}\), be a bent function in \({{\mathcal {D}}}_0\) (outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#})\), where \(\pi =(0, 1, 11, 13, 9, 14, 6, 7, 12, 5, 8, 3, 15, 2, 4, 10)\) is a permutation of \({\mathbb {F}}_2^{4}\) represented in integer form. Using Sage, it was confirmed that r-ind\((g)=1\). Let \(\textbf{c}\in {\mathbb {F}}_2^{8}\) and \(M\in GL(8,{\mathbb {F}}_2^{})\) be arbitrary, say,Let \(S_f=(\textbf{c}\oplus {\mathbb {F}}_2^{8}\cdot M)\wr T_{\delta _0}\wr T_{\delta _0} \subset {\mathbb {F}}_2^{10}\), where \(T_{\delta _0}\) is the truth table of the function \(\delta _0(\textbf{x})\) viewed as a function on \({\mathbb {F}}_2^8\). That is, \(\delta _0(\textbf{x}, \textbf{y})=\delta _0(\textbf{x}) \in {\mathcal {B}}_8\). Then, \(f_i\in {\mathcal {B}}_{10}\) defined via \(S_{f_i}\) and g, using Theorem 3.3, are pairwise disjoint spectra functions, where \(S_{f_{\textbf{a}}}=S_f\oplus {\textbf{q}}_{\textbf{a}}\) and \(\textbf{q}_{\textbf{a}}\in Q=\{{{\textbf {0}}}_8\}\times {\mathbb {F}}_2^{2}\) for \({\textbf{a}} \in {\mathbb {F}}_2^2\). In other words, \({\mathfrak {f}}=(f_{00},f_{01},f_{10},f_{11})\in {\mathcal {B}}_{12}\) is a bent function and can be viewed as a concatenation of four semi-bent functions. Furthermore, using our algorithm in Sect. 3.1, we have confirmed that \({\mathfrak {f}}\) lies outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). The ANF of \({\mathfrak {f}}\) is given by (24) in the appendix.
$$\begin{aligned} \textbf{c}=(0,0,1,0,1,1,1,1),\ \ M=\left( \begin{array}{rrrrrrrr} 0 &{} 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 1 &{} 1 \\ 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 &{} 0 &{} 1 \\ 0 &{} 1 &{} 1 &{} 1 &{} 0 &{} 1 &{} 0 &{} 1 \\ 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 &{} 1 &{} 1 \\ 0 &{} 0 &{} 1 &{} 0 &{} 0 &{} 1 &{} 1 &{} 1 \\ 1 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 \\ 0 &{} 1 &{} 0 &{} 0 &{} 0 &{} 0 &{} 1 &{} 1 \\ 1 &{} 1 &{} 0 &{} 1 &{} 1 &{} 1 &{} 0 &{} 0 \end{array}\right) . \end{aligned}$$
The following remarks are important with respect to the cardinality of bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) or the presence of linear structures of the constituent semi-bent functions.
Remark 3.4
Notice that the number of possibilities of selecting for \(S_{f}\) (which is a binary matrix of size \(2^n\times (n+2)\)) is quite large. We have \(2^n\) possible choices for \(\textbf{c}\in {\mathbb {F}}_2^{n}\) and \(\prod _{k=0}^n (2^n-2^k)\) choices for \(M\in GL(n,{\mathbb {F}}_2^{})\). Thus, for fixed Boolean functions \(t_1,t_2\in {\mathcal {B}}_{n}\), we have \(2^n\prod _{k=0}^n (2^{n}-2^{k})\) choices for \(S_f\). For example, for \(n=8\) this number equals \(\approx 2^{70.2}\).
Remark 3.5
The existence of linear structures in the semi-bent functions \(f_i\), used in Theorem 3.5 to specify \({\mathfrak {f}}\), is of no importance when determining whether \({\mathfrak {f}}\not \in {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). We have confirmed this, using our algorithm from Sect. 3.1, by verifying that the resulting bent functions are always outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) provided that the bent function g used to define the dual of \(f_i\) (by means of (16)) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). It is completely irrelevant whether these semi-bent functions possess linear structures (having affine supports \(S_{f_i}\)) or not. This is also evident from Remark 3.3 since taking \(t_1=t_2=0\) the Walsh supports of the restrictions \(f_{\textbf{a}}\) are affine.
3.4 Four bent decomposition in terms of 5-valued spectra functions
To specify 5-valued spectra Boolean functions, the authors in [14] provided a sufficient and necessary condition that the Walsh spectra of \(f_i\) (corresponding to two different amplitudes) must satisfy, see Sect. 2.2. The notion of totally disjoint spectra functions was also introduced in [14], which can be regarded as a sufficient condition so that the Walsh spectrum specified by (6) is a valid spectrum of a Boolean function.
Definition 3.2
[14, Definition 4.1] For two disjoint sets \(S^{[1]}_f, S^{[2]}_f\subset {\mathbb {F}}^{n}_2\), with \(\#S^{[1]}_f + \# S^{[2]}_f= 2^{\lambda _1}+2^{\lambda _2}< 2^n,\) we say that the dual functions \(f^*_{[1]}:S^{[1]}_f\rightarrow {\mathbb {F}}_2\) and \(f^*_{[2]}:S^{[2]}_f\rightarrow {\mathbb {F}}_2\) (in terms of (6)) are totally disjoint spectra functions if it holds thatfor all \(\mathbf {\mathbf {\textbf{u}}}\in {\mathbb {F}}^n_2\), where \(X_i(\mathbf {\mathbf {\textbf{u}}})=\sum _{\omega \in S^{[i]}_f}(-1)^{f^*_{[i]}(\omega )\oplus \mathbf {\mathbf {\textbf{u}}}\cdot \omega }\), for \(i=1,2\).
$$\begin{aligned} X_1(\mathbf {\mathbf {\textbf{u}}})X_2(\mathbf {\mathbf {\textbf{u}}})=0\;\;\;\text {and}\;\;\;|X_1(\mathbf {\mathbf {\textbf{u}}})|+|X_2(\mathbf {\mathbf {\textbf{u}}})|>0, \end{aligned}$$
Remark 3.6
Note that the second condition implies the nonexistence of a vector \(\mathbf {\mathbf {\textbf{u}}}\in {\mathbb {F}}^n_2\) for which \(X_1(\mathbf {\mathbf {\textbf{u}}})=X_2(\mathbf {\mathbf {\textbf{u}}})=0\). Without this condition, the notion of totally disjoint spectra coincides with non-overlap disjoint spectra functions in [25].
Furthermore, a generic method of specifying totally disjoint spectra functions was also given in [14].
Construction 1
[14] Let n, m and k be even with \(n=m+k\). Let \(h\in {\mathcal {B}}_m\) and \(g\in {\mathcal {B}}_k\) be two bent functions. Let H be any subspace of \({\mathbb {F}}^m_2\) of co-dimension 1, and let \(\overline{H}={\mathbb {F}}^m_2\backslash H\). Let also \(E_1={\mathbb {F}}^k_2\times H\) and \(E_2=\{{{\textbf {0}}}_k\}\times \overline{H}\). The Walsh spectrum of \(f\in {\mathcal {B}}_n\), with \(({\varvec{\alpha }}, {\varvec{\beta }})\in {\mathbb {F}}_2^k \times {\mathbb {F}}_2^m\), can be constructed as follows:Then, \(W_f\) is a valid spectrum of a Boolean function \(f\in {\mathcal {B}}_n\). Let nowThen, \(f_1:E_1 \rightarrow {\mathbb {F}}_2\) and \(f_2:E_2 \rightarrow {\mathbb {F}}_2\) are totally disjoint spectra functions.
$$\begin{aligned} W_{f}({\varvec{\alpha }}, {\varvec{\beta }})= {\left\{ \begin{array}{ll} (-1)^{g({\varvec{\alpha }})\oplus h({\varvec{\beta }})}\cdot 2^{n/2},&{} ({\varvec{\alpha }},{\varvec{\beta }})\in E_1\\ (-1)^{h({\varvec{\beta }})}\cdot 2^{m/2+k},&{} ({\varvec{\alpha }},{\varvec{\beta }})\in E_2\\ 0,&{} otherwise. \end{array}\right. } \end{aligned}$$
(18)
$$\begin{aligned} f_1({\varvec{\alpha }},{\varvec{\beta }})= & {} g({\varvec{\alpha }})\oplus h({\varvec{\beta }}),~~({\varvec{\alpha }}, {\varvec{\beta }})\in E_1\\ f_2({\varvec{\alpha }},{\varvec{\beta }})= & {} h({\varvec{\beta }}),~~({\varvec{\alpha }},{\varvec{\beta }})\in E_2. \end{aligned}$$
Remark 3.7
Notice that the sets \(E_1\) and \(E_2\) in Construction 1 can be defined similarly using any element \(\textbf{v} \in {\mathbb {F}}_2^k\) instead of \(\textbf{0}_k\), so that \(E_2=\{{{\textbf {v}}}\}\times \overline{H}\) and \(E_1={\mathbb {F}}^k_2\times H\) remains the same. Then, \(E_1\) and \(E_2\) are clearly disjoint.
Now, we need to specify a quadruple of 5-valued spectra functions in \({\mathcal {B}}_{n-2}\) by means of Construction 1, which additionally satisfies the condition given by item (iii) of Theorem 2.2. More precisely: When \(k=2\), Construction 1 can generate suitable quadruples of 5-valued spectra functions (which are individually totally disjoint spectra functions) as shown below. Notice that the subspaces \(S_{f_i}^{[1]}\) will correspond to \(E_2^{(i)}\) and \(S_{f_i}^{[2]}\) to \(E_1^{(i)}\) in Theorem 3.6.
(a)
The sets \(S^{[1]}_{f_i}=\{{\varvec{\vartheta }}\in {\mathbb {F}}^{n-2}_2:|W_{f_i}({\varvec{\vartheta }})|=2^{\frac{n}{2}}\}\) \((i\in [1,4])\) are pairwise disjoint;
(b)
All \(S^{[2]}_{f_i}=\{{\varvec{\vartheta }}\in {\mathbb {F}}^{n-2}_2:|W_{f_i}({\varvec{\vartheta }})|=2^{\frac{n-2}{2}}\}\) are equal \((i\in [1,4])\), and for \(f^*_{[2],i}:S^{[2]}_{f_i}\rightarrow {\mathbb {F}}_2\) it holds that \(f^*_{[2],1}\oplus f^*_{[2],2}\oplus f^*_{[2],3}\oplus f^*_{[2],4}=1\).
Theorem 3.6
Let \(n=m+2\) be even so that m is also even. Let \(h\in {\mathcal {B}}_m\) and \(g\in {\mathcal {B}}_k={\mathcal {B}}_2\) be two bent functions. Let H be any subspace of \({\mathbb {F}}^m_2\) of co-dimension 1, and let \(\overline{H}={\mathbb {F}}^m_2\backslash H\). Let also \(E_1^{(i)}={\mathbb {F}}^2_2\times H\) and \(E_2^{(i)}=\{\textbf{c}^{(i)}\}\times \overline{H}\), for \(i=1,\ldots ,4\), where \(\textbf{c}^{(i)} \in {\mathbb {F}}_2^2\) are ordered lexicographically so that \(\textbf{c}^{(i)} \ne \textbf{c}^{(j)}\) for \(1 \le i \ne j \le 4\). We specify the spectra of \(f_{i}\in {\mathcal {B}}_n\) as follows:where \(d=1\) if \(i=4\), otherwise \(d=0\). Then, the function \(f \in {\mathcal {B}}_{n+2}\) given as the concatenation \(f=f_{1}||f_{2}||f_{3} ||f_{4}\) is a bent function.
$$\begin{aligned} W_{f_{i}}({\varvec{\alpha }},{\varvec{\beta }})= {\left\{ \begin{array}{ll} (-1)^{g({\varvec{\alpha }})\oplus h({\varvec{\beta }}){\oplus } d}\cdot 2^{n/2},&{} ({\varvec{\alpha }},{\varvec{\beta }})\in E_1^{(i)}\\ (-1)^{h({\varvec{\beta }})}\cdot 2^{\frac{n-2}{2}+2},&{} ({\varvec{\alpha }},{\varvec{\beta }})\in E_2^{(i)}\\ 0,&{} otherwise, \end{array}\right. } \end{aligned}$$
(19)
Proof
The functions \( f_{i}\in {\mathcal {B}}_n\), specified by (19), are clearly 5-valued spectra functions. We need to verify that their spectra corresponds to Boolean functions. By Construction 1, corresponding to the definition of \(E_1^{(1)}\) and \(E_2^{(1)}\) using \(\textbf{c}^{(1)}=(0,0)\), this is true for \(f_{1}\). Due to the definition of \(E_1^{(i)}\) and \(E_2^{(i)}\) and Remark 3.7, the same is true for any \(f_{i}\) which are all Boolean 5-valued spectra functions. For instance, using \(\textbf{c}^{(2)}=(0,1)\) to define \(f_2\), the condition that \(E_1^{(1)}=E_1^{(2)}\) is clearly true and furthermore \((0,0) \times \overline{H} \cap (0,1) \times \overline{H}=\emptyset \), that is \(E_2^{(1)} \cap E_2^{(2)}=\emptyset \).
Now, the condition for a valid 4-decomposition into 5-valued spectra functions is given by (iii) in Theorem 2.2. The supports \(E_2^{(i)}\) are clearly disjoint by their definition, whereas \(E_1^{(i)}\) are defined on the same subspace of \({\mathbb {F}}_2^n\). The last condition that the bent duals defined on \(E_1^{(i)}\) satisfy \(f^*_{[2],1}\oplus f^*_{[2],2}\oplus f^*_{[2],3}\oplus f^*_{[2],4}=1\) follows from the specification of the spectra on \(E_1^{(i)}\), using the fact that \(d=1\) only when \(i=4\). \(\square \)
Remark 3.8
Since \(d=1\) when \(i=4\), the complement of the dual is used for the fourth constituent function \(f_4\). This ensures that the bent duals satisfy \(f^*_{[2],1}\oplus f^*_{[2],2}\oplus f^*_{[2],3}\oplus f^*_{[2],4}=1\). Nevertheless, this is not the only choice and the bent duals can be specified in other ways (through the complement operation) as long as their sum equals 1.
The following examples illustrate the details of this construction and the possibility of getting bent functions outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). Notice that the dual h used to specify f is not necessarily in \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\).
Example 3.3
Let \(n=8\) and let \(h\in {\mathcal {B}}_6,g\in {\mathcal {B}}_2\) be defined by \(h(x_0,\ldots ,x_5)=x_0x_1\oplus x_2x_3\oplus x_4x_5 \in {{{\mathcal {M}}}{{\mathcal {M}}}}\) and \(g(x_0,x_1)=x_0x_1\). Let \(H=\langle (1,0,0,0,0,0)\rangle ^{\perp }\subset {\mathbb {F}}_2^{6}\) be a subspace of codimension 1. Using the mathematical software Sage, we constructed the functions \(f^{(i)}\in {\mathcal {B}}_8\) for \(i=1,\ldots ,4\) defined by (19) and their ANF’s are given as follows: Then, the function \(f\in {\mathcal {B}}_{10}\) given as the concatenation \(f=f_{1}||f_2||f_3||f_{4}\) is a cubic bent function defined by Using our algorithm in Sect. 3.1, we could verify that \(f \in {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
$$\begin{aligned} f_1(x_0,\ldots ,x_7)&=x_0x_1x_3 \oplus x_0x_1 \oplus x_2x_3 \oplus x_4x_5 \oplus x_6x_7,\\ f_2(x_0,\ldots ,x_7)&= x_0x_1x_3 \oplus x_0x_1 \oplus x_0x_3 \oplus x_2x_3 \oplus x_4x_5 \oplus x_6x_7,\\ f_3(x_0,\ldots ,x_7)&= x_0x_1x_3 \oplus x_0x_1 \oplus x_1x_3 \oplus x_2x_3 \oplus x_4x_5 \oplus x_6x_7,\\ f_4(x_0,\ldots ,x_7)&= x_0x_1x_3 \oplus x_0x_1 \oplus x_0x_3 \oplus x_1x_3 \oplus x_2x_3 \oplus x_3 \oplus x_4x_5 \oplus x_6x_7 \oplus 1 \end{aligned}$$
$$\begin{aligned} f(x_0,\ldots ,x_9)=x_1x_2x_3 \oplus x_1x_2 \oplus x_1x_3x_8 \oplus x_2x_3x_9 \oplus x2x_3 \oplus x_3x_8x_9 \oplus x_4x_5 \oplus x_6x_7 \oplus x_8x_9. \end{aligned}$$
On the other hand, the following two examples illustrate that selecting the dual h to be outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\), the resulting bent functions (constructed using Theorem 3.6) are outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\).
Example 3.4
Let \(h\in {\mathcal {B}}_8\) defined by \(h(x,y)=Tr_1^4(xy^7)+\delta _0(x),\ x,y\in {\mathbb {F}}_{2^4}\), be a bent function in the class \({{\mathcal {D}}}_0\setminus {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) [4, 28], and let \(g\in {\mathcal {B}}_2\) be defined by \(g(x_0,x_1)=x_0x_1\). Let us define \(H=\langle (1,0,0,0,0,0,0,0)\rangle ^{\perp }\subset {\mathbb {F}}_2^{8}\) to be a subspace of codimension 1. Using Sage we constructed the functions \(f_{i}\in {\mathcal {B}}_{10}\) for \(i=1,\ldots ,4\) defined by (19). Then, the function \(f\in {\mathcal {B}}_{12}\) given as \(f=f_{1}||f_2||f_3||f_{4}\) is a bent function of algebraic degree 5. This time the function f, whose ANF is given by (22) in the appendix, is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
Example 3.5
Let \(n=10\) and \(h\in {\mathcal {B}}_8,g\in {\mathcal {B}}_2\) be bent functions, where \(g(x_0,x_1)=x_0x_1\). The function \(h\in {\mathcal {B}}_8\), whose ANF is given by (21) in Appendix, lies in \({{\mathcal {P}}}{{\mathcal {S}}}^{\#}\) and is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\). Using Sage, we constructed the functions \(f_{i}\in {\mathcal {B}}_{10}\) for \(i=1,\ldots ,4\) defined by (19). Then, the function \(f\in {\mathcal {B}}_{12}\) given as \(f=f_{1}||f_2||f_3||f_{4}\) is a bent function of algebraic degree 5. Again, it could be confirmed that f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\) (its ANF is given by (23) in the appendix).
The above examples indicate that the conclusions (related to the dual) given in Sect. 3.2 seem to be applicable in this case as well. More precisely, the class belongingness of f in Theorem 3.6 is strongly related to the choice of the dual bent functions.
Theorem 3.7
Let \(f \in {\mathcal {B}}_{n+2}\) be constructed by means of Theorem 3.6, thus \(f=f_1|| f_2||f_3 ||f_4\) where \(f_i \in {\mathcal {B}}_n\). If the dual bent function \(h \in {\mathcal {B}}_{n-2}\) in Theorem 3.6 is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\), then f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\).
Proof
By Remark 3.1, f is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) if and only if its dual \(f^*\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). Hence, it is enough to show that \(f^*\) is outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). The “duals” of the restrictions \(f_i\) are actually given by (19). By the definition of \(f^*\), we have that \((-1)^{f^*(\mathbf {\mathbf {\textbf{u}}})}=2^{-\frac{n+2}{2}}W_f(\mathbf {\mathbf {\textbf{u}}})\) for any \(\textbf{u} \in {\mathbb {F}}_2^{n+2}\), since \(f \in {\mathcal {B}}_{n+2}\). For convenience, we write \(\mathbf {\mathbf {\textbf{u}}}=({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }}) \in {\mathbb {F}}_2^2 \times {\mathbb {F}}_2^m \times {\mathbb {F}}_2^2\) with \(n=m+2\) as used in Theorem 3.6. We notice that in general, using that \(\textbf{x}=(\textbf{x}',x_{n+1}, x_{n+2}) \in {\mathbb {F}}_2^n \times {\mathbb {F}}_2 \times {\mathbb {F}}_2\), we haveHence, for any fixed \(\gamma \in {\mathbb {F}}_2^2\), we can compute the value of \(W_f({\varvec{\alpha }},{\varvec{\beta }}, {\varvec{\gamma }})\) by using the Walsh spectra of the constituent functions \(f_i\).
$$\begin{aligned} W_f({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})= & {} \sum _{\textbf{x} \in {\mathbb {F}}_2^n \times {\mathbb {F}}_2^2}(-1)^{f(\textbf{x}) + \mathbf {\mathbf {\textbf{u}}} \cdot \textbf{x}} \nonumber \\= & {} \sum _{\textbf{x} \in {\mathbb {F}}_2^n \times (0,0)}(-1)^{f(\textbf{x}',0,0) + ({\varvec{\alpha }},{\varvec{\beta }}) \cdot \textbf{x}' } + \sum _{\textbf{x} \in {\mathbb {F}}_2^n \times (0,1)}(-1)^{f(\textbf{x}',0,1) + ({\varvec{\alpha }}, {\varvec{\beta }}) \cdot \textbf{x}' + \gamma _2} \nonumber \\{} & {} \quad + \sum _{\textbf{x} \in {\mathbb {F}}_2^n \times (1,0)}(-1)^{f(\textbf{x}',1,0) + ({\varvec{\alpha }}, {\varvec{\beta }}) \cdot \textbf{x}' + \gamma _1} \nonumber \\{} & {} \quad +\sum _{\textbf{x} \in {\mathbb {F}}_2^n \times (1,1)}(-1)^{f(\textbf{x}',1,1) + ({\varvec{\alpha }}, {\varvec{\beta }}) \cdot \textbf{x}' + \gamma _1 + \gamma _2}\nonumber \\= & {} W_{f_1}({\varvec{\alpha }},{\varvec{\beta }}) + (-1)^{\gamma _2} W_{f_2}({\varvec{\alpha }},{\varvec{\beta }}) \nonumber \\{} & {} \quad + (-1)^{\gamma _1}W_{f_3}({\varvec{\alpha }},{\varvec{\beta }}) + (-1)^{\gamma _1 + \gamma _2}W_{f_4}({\varvec{\alpha }},{\varvec{\beta }}). \end{aligned}$$
(20)
We first notice that \(W_{f_i}({\varvec{\alpha }},{\varvec{\beta }})= (-1)^{h({\varvec{\beta }})}\cdot 2^{\frac{n-2}{2}+2}\) when \(({\varvec{\alpha }},{\varvec{\beta }})\in E_2^{(i)}\), and furthermore by construction the sets \(E_2^{(i)}\) are mutually disjoint for \(i=1,\ldots ,4\). Hence, if for instance \(({\varvec{\alpha }},{\varvec{\beta }})\in E_2^{(1)}\) then \(W_{f_1}({\varvec{\alpha }},{\varvec{\beta }})= (-1)^{h({\varvec{\beta }})}\cdot 2^{\frac{n-2}{2}+2}\) and \(W_{f_i}({\varvec{\alpha }},{\varvec{\beta }})=0\) for \(2 \le i \le 4\), which implies that \(W_f({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})= (-1)^{h({\varvec{\beta }})}\cdot 2^{\frac{n}{2}+1}\) when \(({\varvec{\alpha }},{\varvec{\beta }})\in E_2^{(1)}\). The other cases when \((\alpha ,\beta )\in E_2^{(i)}\) for \(i \ne 1\) are similar.
Now, considering the case \(({\varvec{\alpha }},{\varvec{\beta }})\in E_1^{(i)}\), we first notice that \(E_1:=E_1^{(1)}= \cdots = E_1^{(4)}\) (by construction), where \(E_1={\mathbb {F}}_2^2 \times H\) as in Theorem 3.6. In addition, \(W_{f_i}({\varvec{\alpha }},{\varvec{\beta }})=(-1)^{g({\varvec{\alpha }})\oplus h({\varvec{\beta }}) + d}\cdot 2^{n/2}\), where \(d=1\) when \(i=4\) only. This also implies that \(W_{f_1}({\varvec{\alpha }},{\varvec{\beta }})=W_{f_2}({\varvec{\alpha }}, {\varvec{\beta }})=W_{f_3}({\varvec{\alpha }},{\varvec{\beta }})= - W_{f_4}({\varvec{\alpha }},{\varvec{\beta }})\) when \(({\varvec{\alpha }},{\varvec{\beta }})\in E_1\). Therefore, using (20), we haveHence, \(W_{f}({\varvec{\alpha }},{\varvec{\beta }},\gamma _1,\gamma _2)= 2 \cdot 2^{n/2}(-1)^{g({\varvec{\alpha }})\oplus h({\varvec{\beta }}) \oplus \gamma _1\gamma _2}\) when \(({\varvec{\alpha }},{\varvec{\beta }})\in E_1\), where \(g({\varvec{\alpha }})\oplus h({\varvec{\beta }}) \oplus \gamma _1\gamma _2\) falls into the framework of Theorem 3.1 and additionally Remark 3.1 applies. Notice that the case \(({\varvec{\alpha }},{\varvec{\beta }}) \not \in E_1\) and at the same time having \(W_{f_i}({\varvec{\alpha }},{\varvec{\beta }})=0\) is already covered above since then \(({\varvec{\alpha }},{\varvec{\beta }}) \in E_2^{(j)}\) for some \(j \ne i\). This is a consequence of the fact that \(E_1 \cup (\cup _{i=1}^4 E_2^{(i)}) ={\mathbb {F}}_2^n\).
$$\begin{aligned} W_{f}({\varvec{\alpha }},{\varvec{\beta }},0,0)= & {} W_{f_1}({\varvec{\alpha }},{\varvec{\beta }}) + W_{f_2}({\varvec{\alpha }},{\varvec{\beta }})+W_{f_3}({\varvec{\alpha }},{\varvec{\beta }}) - W_{f_4}({\varvec{\alpha }},{\varvec{\beta }})=2W_{f_1}({\varvec{\alpha }},{\varvec{\beta }}) \\ W_{f}({\varvec{\alpha }},{\varvec{\beta }},0,1)= & {} W_{f_1}({\varvec{\alpha }},{\varvec{\beta }}) - W_{f_2}({\varvec{\alpha }},{\varvec{\beta }})+W_{f_3}({\varvec{\alpha }},{\varvec{\beta }}) + W_{f_4}({\varvec{\alpha }},{\varvec{\beta }})=2W_{f_1}({\varvec{\alpha }},{\varvec{\beta }})\\ W_{f}({\varvec{\alpha }},{\varvec{\beta }},1,0)= & {} W_{f_1}({\varvec{\alpha }},{\varvec{\beta }}) + W_{f_2}({\varvec{\alpha }},{\varvec{\beta }})-W_{f_3}({\varvec{\alpha }},{\varvec{\beta }}) + W_{f_4}({\varvec{\alpha }},{\varvec{\beta }})=2W_{f_1}({\varvec{\alpha }},{\varvec{\beta }})\\ W_{f}({\varvec{\alpha }},{\varvec{\beta }},1,1)= & {} W_{f_1}({\varvec{\alpha }},{\varvec{\beta }}) - W_{f_2}({\varvec{\alpha }},{\varvec{\beta }})-W_{f_3}({\varvec{\alpha }},{\varvec{\beta }}) - W_{f_4}({\varvec{\alpha }},{\varvec{\beta }})=-2W_{f_1}({\varvec{\alpha }},{\varvec{\beta }}). \end{aligned}$$
To summarize, the dual \(f^*\) is equal to \(g({\varvec{\alpha }})\oplus h({\varvec{\beta }}) \oplus \gamma _1\gamma _2\) when \(f^*\) is restricted to the subspace \(({\varvec{\alpha }},{\varvec{\beta }},{\varvec{\gamma }})\in E_1 \times {\mathbb {F}}_2^2\) and to \(h({\varvec{\beta }})\) when \(f^*\) is restricted to the complement of \(E_1 \times {\mathbb {F}}_2^2\). Notice that g is a 2-variable quadratic bent function, thus \(g(\alpha _1,\alpha _2)=\alpha _1\alpha _2\). Therefore, using the assumption that \(h \not \in {{{\mathcal {M}}}{{\mathcal {M}}}}^\#\), Remark 3.1 and Corollary 1 imply that \(f^* \not \in {{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) and hence \(f \not \in {{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). \(\square \)
Remark 3.9
The condition on the dual bent function \(h \in {\mathcal {B}}_{n-2}\) to be outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) is strictly sufficient and not necessary. There exist bent functions \(\{f\}\) in eight variables, represented as \(f=f_1||f_2||f_3||f_4\) where \(f_i\) are 5-valued spectra functions, that are outside \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\). Since in this case the dual bent function h is defined on \({\mathbb {F}}_2^4\) it apparently belongs to \({{{\mathcal {M}}}{{\mathcal {M}}}}\).
4 5-valued spectra functions from the generalized MM class
Another method of specifying 5-valued spectra functions, also given in [14], uses the generalized Maiorana-McFarland class (GMM) of Boolean functions. For convenience and ease of notation, we use the variable set \(x_0, \ldots , x_{n-1}\) instead of \(x_1,\ldots ,x_n\) for functions on \({\mathbb {F}}_2^n\).
Theorem 4.1
[14] Let \(E_0\subset {\mathbb {F}}_2^s\) with \(1\le s\le \lfloor n/2\rfloor \). Let \(E_1=\overline{E_0}\times {\mathbb {F}}_2^t\), where \(\overline{E_0}={\mathbb {F}}_2^s\backslash E_0\) and \(0\le t\le \lfloor n/2\rfloor \). Let \(\phi _0\) be an injective mapping from \(E_0\) to \({\mathbb {F}}_2^{n-s}\), and \(\phi _1\) be an injective mapping from \(E_1\) to \({\mathbb {F}}_2^{n-s-t}\). Let \(X=(x_0,\ldots ,x_{n-1})\in {\mathbb {F}}_2^n\) and \(X_{(i,j)}=(x_i,\ldots ,x_j)\in {\mathbb {F}}_2^{j-i+1}\). Let \(f\in {\mathcal {B}}_n\) be defined as follows:LetandThen, we have
$$\begin{aligned} f(X)= {\left\{ \begin{array}{ll} \phi _0(X_{{(0,s-1)}})\cdot X_{{(s,n-1)}},&{} if~X_{{(0,s-1)}}\in E_0\\ \phi _1(X_{{(0,s+t-1)}})\cdot X_{{(s+t,n-1)}},&{} if~X_{{(0,s+t-1)}}\in E_1. \end{array}\right. } \end{aligned}$$
$$\begin{aligned} T_0=\{\phi _0({\varvec{\eta }})\mid {\varvec{\eta }}\in E_0\}, \end{aligned}$$
$$\begin{aligned} T_1=\{\phi _1({\varvec{\theta }})\mid {\varvec{\theta }}\in E_1\}. \end{aligned}$$
(a)
\(W_f({\varvec{\omega }})\in \{0,\pm 2^{n-s},\pm 2^{n-s-t}\}\) if \(t\ne 0\) and \(T_0\subset {\mathbb {F}}_2^t\times \overline{T_1}\), where \(\overline{T_1}={\mathbb {F}}_2^{n-s-t}\backslash T_1\);
(b)
\(W_f({\varvec{\omega }})\in \{0,\pm 2^{n-s},\pm 2^{n-s+1}\}\) if \(t=0\), \(T_0\cap T_1\ne \emptyset \) and \(T_0\ne T_1\).
Example 4.1
Let \(n=8,s=3\) and \(t=1\). Now, we employ Theorem 4.1 to construct 5-valued spectra functions \(f^{(1)},\ldots ,f^{(4)}\) that satisfy Theorem 2.2. The resulting function \(f=f^{(1)}||f^{(2)}||f^{(3)}||f^{(4)}\in {\mathcal {B}}_{10}\) is then bent. Let \({\mathbb {F}}_2^r=\{\textbf{v}_0^{(r)},\ldots ,\textbf{v}_{2^r-1}^{(r)}\}\) denote the lexicographically ordered r-dimensional vector space over \({\mathbb {F}}_{2^{}}\).
Furthermore, we note that all sets defined below are also lexicographically ordered. We define \(E_0=\{\textbf{e}_{0}^{(0)},\textbf{e}_{1}^{(0)},\textbf{e}_{2}^{(0)}\}\), where \(\textbf{e}_i^{(0)}=\textbf{v}_i^{(3)}\in {\mathbb {F}}_2^3\) for \(i=0,1,2\) (hence \(\textbf{e}_{0}^{(0)}=(0,0,0),\textbf{e}_{1}^{(0)}=(0,0,1),\textbf{e}_{2}^{(0)}=(0,1,0)\)),
and \(E_1=\overline{E_0}\times {\mathbb {F}}_2=\{\textbf{e}_{0}^{(1)},\textbf{e}_{1}^{(1)},\ldots ,\textbf{e}_{9}^{(1)}\}\subset {\mathbb {F}}_2^4\), where \(\overline{E_0}={\mathbb {F}}_2^3{\setminus } E_0\). Let \(\phi _1:E_1\rightarrow {\mathbb {F}}_2^4\) be defined byfor \(i=0,\ldots ,9\) Let \(T_1=\{\phi _1({\varvec{\theta }}):{\varvec{\theta }}\in E_1\}\) and \(\overline{T_1}={\mathbb {F}}_2^4\setminus T_1\), where clearly \(|\overline{T_1}|=6\). Let \(\Gamma ={\mathbb {F}}_2\times \overline{T_1}=\{{\varvec{\gamma }}_0,\ldots ,{\varvec{\gamma }}_{11}\}\subset {\mathbb {F}}_2\times {\mathbb {F}}_2^4={\mathbb {F}}_2^5\) and let \(\phi _0^{(j)}:E_0\rightarrow {\mathbb {F}}_2^5\) be defined byfor \(j=1,\ldots ,4\).
$$\begin{aligned} \phi _1(\textbf{e}_{i}^{(1)})=\textbf{v}_{i}^{(4)}, \end{aligned}$$
$$\begin{aligned} \phi _0^{(j)}(\textbf{e}_{i}^{(0)})={\varvec{\gamma }}_{i+3j},\ \textbf{e}_{i}^{(0)}\in E_0, \end{aligned}$$
If \(T_0^{(j)}=\{\phi _0^{(j)}({\varvec{\eta }}):{\varvec{\eta }} \in E_0\}\), then \(T_0^{(j)}\subset {\mathbb {F}}_2\times \overline{T_1}\) (as required in Theorem 4.1-(a)), for \(j=1,\ldots ,4\). Now let \(X=(x_0,\ldots ,x_{7})\in {\mathbb {F}}_2^{8}\) and \(X_{(i,j)}=(x_i,\ldots ,x_j)\in {\mathbb {F}}_2^{j-i+1}\). For \(j=1,2,3,4\), \(f^{(j)}\in {\mathcal {B}}_{8}\) is defined as follows:where \(\delta _1(j)=1\) for \(j=1\) and 0 otherwise. Let \(S_1^{(j)}=\{\textbf{x}\in {\mathbb {F}}_2^{8}:|W_{f^{(j)}}(\textbf{x})|=2^5\}\) and \(S_2^{(j)}=\{\textbf{x}\in {\mathbb {F}}_2^{8}:|W_{f^{(j)}}(\textbf{x})|=2^4\}\). Using Sage we could verify that all \(S_1^{(j)}\) are pairwise disjoint and all \(S_2^{(j)}\) are equal. Furthermore, by the construction, \(f^{*}_{[2],1}\oplus \cdots \oplus f^{*}_{[2],4}=1\). Hence, by Theorem 2.2, the function \(f=f^{(1)}||f^{(2)}||f^{(3)}||f^{(4)}\in {\mathcal {B}}_{10}\) of algebraic degree 5 is bent, and its ANF is defined by:Nevertheless, using our algorithm in Sect. 3.1 implemented in Sage, we could confirm that \(f\in {{{\mathcal {M}}}{{\mathcal {M}}}}^{\#}\).
$$\begin{aligned} f^{(j)}(X)= {\left\{ \begin{array}{ll} \phi _0^{(j)}(X_{(0,2)})\cdot X_{(3,7)}+\delta _1(j),&{} if~X_{(0,2)}\in E_0\\ \phi _1(X_{(0,3)})\cdot X_{(4,7)}+\delta _1(j),&{} if~X_{(0,3)}\in E_1, \end{array}\right. } \end{aligned}$$
$$\begin{aligned}{} & {} f(x_0,\ldots ,x_9)=x_{0} x_{1} x_{2} x_{3} x_{4} \oplus x_{0} x_{1} x_{2} x_{3} x_{9} \oplus x_{0} x_{1} x_{2} x_{4} x_{8} \oplus x_{0} x_{1} x_{2} x_{4} \oplus x_{0} x_{1} x_{2} x_{6}\\{} & {} \quad \oplus x_{0} x_{1} x_{3} x_{4} \oplus x_{0} x_{1} x_{3} x_{9} \oplus x_{0} x_{1} x_{4} x_{8} \oplus x_{0} x_{1} x_{4} \oplus x_{0} x_{1} x_{6} \oplus x_{0} x_{1} x_{7} \\{} & {} \quad \oplus x_{0} x_{2} x_{4} \oplus x_{0} x_{2} x_{5} x_{8} \oplus x_{0} x_{2} x_{5} \oplus x_{0} x_{2} x_{6} \oplus x_{0} x_{4} \oplus x_{0} x_{5} x_{8} \oplus x_{1} x_{2} x_{5} \oplus x_{1} x_{2} x_{6} x_{8} \oplus x_{1} x_{5} \\{} & {} \quad \oplus x_{1} x_{6} x_{8} \oplus x_{1} x_{6} \oplus x_{2} x_{3} x_{4} \oplus x_{2} x_{3} x_{9} \oplus x_{2} x_{4} x_{8} \oplus x_{2} x_{5} x_{8} \oplus x_{2} x_{6} x_{8}\\{} & {} \quad \oplus x_{2} x_{7} \oplus x_{3} x_{9} \oplus x_{4} x_{8} \oplus x_{5} x_{8} \oplus x_{5} \oplus x_{6} x_{8} \oplus x_{7} \oplus x_{8} x_{9} \oplus x_{8} \oplus x_{9} \oplus 1. \end{aligned}$$
As a generalization of the previous example, we give the following result.
Remark 4.1
We assume that all sets defined in Theorem 4.2 are ordered lexicographically, and with \({\mathbb {F}}_2^k=\{\textbf{v}_0^{(k)},\textbf{v}_1^{(k)},\ldots ,\textbf{v}_{2^k-1}^{(k)}\}\) (for suitable k) we will denote the elements of the lexicographically ordered k-dimensional vector space over \({\mathbb {F}}_{2^{}}\).
Theorem 4.2
Let \(n=2\,m\ge 8\), \(s=m-1\), and \(E_0=\{\textbf{v}_0^{(m-1)},\ldots ,\textbf{v}_{\tau -1}^{(m-1)}\} { \subset {\mathbb {F}}_2^{m-1}}\) where \(\tau <2^s-1\) and \(4\tau \le 2^{m+1}\). Define \(E_1=\overline{E_0}\times {\mathbb {F}}_2=\{\textbf{e}_0^{(1)},\ldots ,\textbf{e}_{\lambda }^{(1)}\} { \subset {\mathbb {F}}_2^{m}}\), where \(\lambda =2\cdot (2^{m-1}-\tau )-1\) and \(\overline{E_0}={\mathbb {F}}_2^{m-1}{\setminus } E_0\). Let \(\phi _1:E_1\rightarrow {\mathbb {F}}_2^{m}\) be an injective mapping defined byfor \(i=0,1,\ldots ,\lambda \), whose image set is denoted by \(T_1=\{\phi _1({\varvec{\theta }}): {\varvec{\theta }} \in E_1\}\). Now, denoting \(\Gamma ={\mathbb {F}}_2\times ({\mathbb {F}}_2^{m}{\setminus } T_1)=\{{\varvec{\gamma }}_0,{\varvec{\gamma }}_1,\ldots ,{\varvec{\gamma }}_{4\tau -1}\}\), let \(\phi _0^{(j)}:E_0\rightarrow \Gamma \subset {\mathbb {F}}_2^{m+1}\), for \(j=1,\ldots ,4\), be injective mappings defined byLet \(X=(x_0,\ldots ,x_{n-1})\in {\mathbb {F}}_2^{n}\) and \(X_{(i,j)}=(x_i,\ldots ,x_j)\in {\mathbb {F}}_2^{j-i+1}\). For \(j=1,\ldots ,4\), \(f^{(j)}\in {\mathcal {B}}_{n}\) is defined as follows:where \(\delta _1(j)=1\) for \(j=1\) and 0 otherwise. Then, the function \(f\in {\mathcal {B}}_{n+2}\) given as the concatenation \(f=f^{(1)}||f^{(2)}||f^{(3)}||f^{(4)}\) is a bent function.
$$\begin{aligned} \phi _1(\textbf{e}_i^{(1)})=\textbf{v}_i^{(m)},\ \textbf{e}_i^{(1)}\in E_1, \end{aligned}$$
$$\begin{aligned} \phi _0^{(j)}(\textbf{e}_i^{(0)})={\varvec{\gamma }}_{i+\tau (j-1)},\ \textbf{e}_i^{(0)}\in E_0. \end{aligned}$$
$$\begin{aligned} f^{(j)}(X)= {\left\{ \begin{array}{ll} \phi _0^{(j)}(X_{(0,m-2)})\cdot X_{(m-1,n-1)}+\delta _1(j),&{} if~X_{(0,m-2)}\in E_0\\ \phi _1(X_{(0,m-1)})\cdot X_{(m,n-1)}+\delta _1(j),&{} if~X_{(0,m-1)}\in E_1, \end{array}\right. } \end{aligned}$$
Proof
Firstly, we note that \(W_{f^{(j)}}(\textbf{x})\in \{0,\pm 2^m,\pm 2^{m+1}\}\) by Theorem 4.1, for \(j=1,\ldots ,4\) (with \(s=m-1\) and \(t=1\)). It remains to show that these functions satisfy the conditions of Theorem 2.2iii).
Let \(S_{f^{(j)}}^{[1]}=\{\textbf{x}\in {\mathbb {F}}_2^n:|W_{f^{(j)}}(\textbf{x})|=2^{m+1}\) and \(S_{f^{(j)}}^{[2]}=\{\textbf{x}\in {\mathbb {F}}_2^n:|W_{f^{(j)}}(\textbf{x})|=2^{m}\), for \(j=1,\ldots ,4\). The cardinality of \(\Gamma \) can be computed asBecause \(|\Gamma |=4\tau \le 2^{m+1}\) and \(|\phi _0^{(j)}(E_0)|=\tau \), it is easy to see that \(\phi _0^{(j)}\) splits \(\Gamma \) into 4 disjoint subsets, that is, \(\Gamma =\bigcup _{j=1}^4\phi ^{(j)}_0(E_0)\) and \(\phi ^{(j)}_0(E_0)\cap \phi ^{(j')}_0(E_0)=\emptyset \) for \(j\ne j'\).
$$\begin{aligned} |\Gamma |&=2\cdot |{\mathbb {F}}_2^m\setminus T_1|=2(2^m-|E_1|)=2\cdot (2^m-2(2^{m-1}-\tau ))=2^{m+1}-2^{m+1}+4\tau =4\tau . \end{aligned}$$
Consequently, the sets \(S_{f^{(j)}}^{[1]}\) are pairwise disjoint for \(j=1,\ldots ,4\). As the function \(\phi _1\) is the same for all \(f^{(j)}\), it follows that all sets \(S_{f^{(j)}}^{[2]}\) are equal. The condition that the bent duals defined on \(S_{f^{(j)}}^{[2]}\) satisfy \(f^*_{[2],1}\oplus f^*_{[2],2}\oplus f^*_{[2],3}\oplus f^*_{[2],4}=1\), follows from the fact that \(\delta _1(j)=1\) only for \(j=1\). This follows from the fact that \(|W_f(\textbf{x})|=2^m\) is determined by the value of \(\phi _1(X_{(0,m-1)})\cdot X_{(m,n-1)}\) (cf. proof of [14, Theorem V.6]) and consequently the values of \(f^*_{[2],j}\) are the same except for \(j=1\), where we additionally add the constant 1.
Thus, the conditions given in item iii) of Theorem 2.2 are satisfied and \(f=f^{(1)}||f^{(2)}||f^{(3)}||f^{(4)} \in {\mathcal {B}}_{n+2}\) is a bent function. \(\square \)
Remark 4.2
The above statement also holds if \(E_0\) is a collection of arbitrary \(\tau \) elements in \({\mathbb {F}}_2^{m-1}\). However, (partial) computer simulations indicate that this approach only generates bent functions inside the \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) class, regardless of the choice of \(E_0\).
Open Problem 1
Prove or disprove that the bent functions constructed using Theorem 4.2 always belong to \({{{\mathcal {M}}}{{\mathcal {M}}}}^\#\) regardless of the choice of \(E_0\).
5 Conclusions
This article significantly provides several infinite families of bent functions provably outside the completed Maiorana-McFarland class. In the context of enumeration of bent functions, it would be of interest to investigate whether the obtained families, that belong to different cases of 4-decomposition, are fully/partially non-intersecting. Another important question that remains unanswered, due to the lack of indicators for the partial spread class, is whether these families intersect with the \({{\mathcal {P}}}{{\mathcal {S}}}\) class.
Acknowledgements
Enes Pasalic is partly supported by the Slovenian Research Agency (research program P1-0404 and research Projects J1-9108, J1-1694, N1-1059), and the European Commission for funding the InnoRenew CoE project (Grant Agreement No. 739574) under the Horizon2020 Widespread-Teaming program and the Republic of Slovenia (Investment funding of the Republic of Slovenia and the European Union of the European Regional Development Fund). Amar Bapić is supported in part by the Slovenian Research Agency (research program P1-0404 and Young Researchers Grant). Fengrong Zhang is supported in part by the Natural Science Foundation of China (No. 61972400), in part by the Fundamental Research Funds for the Central Universities (XJS221503). Y. Wei is supported in part by the Natural Science Foundation of China (No. 61872103), in part by the Guangxi Natural Science Foundation (2019GXNSFGA245004).
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.