Characterization and Properties of Bent-Negabent Functions

I.   Introduction

Throughout this paper, $\mathbb{F}_{2}^{n}$ be the $n$-dimensional vector space over the field $\mathbb{F}_{2}$ with two elements, $\mathbb{F}_{2^{n}}$ be the finite field consisting $2^{n}$ elements. Let ${\cal{B}}_{n}$ be the set of all $n$-variable Boolean functions. The set of integers, real numbers, and complex numbers are denoted by $\mathbb{Z}$, $\mathbb{R}$, and $\mathbb{C}$, respectively. If $z=r+ti\in\mathbb{C}$, then $|z|= \sqrt{r^{2}+t^{2}}$ denotes the absolute value of $z$, and $\bar{z}=r-ti$ denotes the complex conjugate of $z$, where $i^{2}=-1$, $r,t\in\mathbb{R}$. Let $V_{n}$ denote a vector space of dimension $n$ over $\mathbb{F}_{2}$, we identify $V_{n}$ by $\mathbb{F}_{2}^{n}$ or $\mathbb{F}_{2^{n}}$. Let $\langle \cdot,\cdot\rangle$ denote the inner product on $V_{n}$, then for any $a,x\in V_{n}$

where $a\cdot x=a_{1}x_{1}+\cdots+a_{n}x_{n}$, ${\rm{Tr}}_{1}^{n}(ax)$ denotes the absolute trace of $ax\in\mathbb{F}_{2^{n}}$. For any positive integer $k|n$, the trace function from $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{k}}$ is the mapping defined as

Boolean bent functions were introduced by Rothaus in 1976^[1], which play an important role in both symmetric cryptography and error-correcting codes. An $n$-variable Boolean function from $V_{n}$ to $\mathbb{F}_{2}$ is bent if it has maximal Hamming distance to the set of affine Boolean functions (this maximum distance is the nonlinearity^[2]). The Walsh-Hadamard transform of $f\in {\cal{B}}_{n}$ at $a\in V_{n}$ is defined as

It is a powerful tool for analyzing Boolean functions. A function $f\in{\cal{B}}_{n}$ is bent only if $|{\cal{W}}_{f}(a)|=1$ for all $a\in V_n$, therefore bent functions only exist for $n$ even.

In Ref.[3], the concept of a bent function is extended to some generalized bent criteria for a Boolean function by analyzing Boolean functions that have flat spectrum with respect to one or more transforms from a specified set of unitary transforms.The transforms chosen by Riera and Parker are $n$-fold tensor products of the identity matrix, the Walsh-Hadamard matrix and the nega-Hadamard matrix, respectively:

The Walsh-Hadamard transform can be described as the tensor product of several $H$’s, similarly, if the transform can be represented by the tensor product of several $N$’s, it is called the nega-Hadamard transform. The Walsh-Hadamard transform is an example of a unitary transformation on the space of all Boolean functions. The nega-Hadamard transform of $f(x)$ at $a\in V_{n}$ is the complex valued function

where ${\bf 1}_{n}=(1,1,\ldots,1)$, and

which is a generalization of Walsh-Hadamard transform. A function $f\in {\cal{B}}_n$ is negabent only if $|{\cal{N}}_{f}(a)|=1$ for all $a\in V_{n}$. Unlike bent functions, the negabent functions exist for both even and odd variables. In particular, a negabent function is called bent-negabent if it is also a bent function.

The nega-Hadamard transform is also a powerful tool for analyzing Boolean functions. Recently, some interesting topic focus on the construction methods and characterizations for (bent-) negabent functions^[4-9]. In Ref.[10], Sarkar presented a necessary and sufficient condition such that the quadratic monomial

is bent-negabent. In Ref.[11], Huang et al. further proposed the quadratic polynomial form and proved that the quadratic polynomial

where $c_{i}\in \mathbb{F}_{2^{n}}$ for $1\leq i\leq\frac{n}{2}-1$ and $c_{\frac{n}{2}}\in \mathbb{F}_{2^{\frac{n}{2}}}$ is bent if and only if $L_{f}(x)=\sum_{i=1}^{\frac{n}{2}-1}(c_{i}x^{2^{i}}+c_{i}^{2^{n-i}}x^{2^{n-i}})+c_{\frac{n}{2}}x^{2^{\frac{n}{2}}}$ is a linearized permutation polynomial, that is, $L_{f}(x)=0$ only has a solution 0.

Inspired by Refs.[10, 11], our first contribution is to provide the necessary and sufficient condition such that the quadratic polynomial $f$ defined by Eq.(2) is bent-negabent. From this result, the bent-negabentness of quadratic Boolean functions depends on the corresponding complete mapping polynomial. Our second contribution is to provide a new efficient characterization of negabent functions by using the parity of Hamming weight. This characterization provides a new method for the study of negabent functions.

In addition, Gupt et al.^[12] presented a generalization of the convolution theorem for two $n$-variable Boolean functions, and the Walsh-Hadamard transform of composition of a Boolean function and a vectorial Boolean function from the convolution was provided. Then our third contribution is to present the generalized nega-convolution theorem. Furthermore, we provide the nega-Hadamard transform of composition of a Boolean function and a vectorial Boolean function. By this method, the nega-Hadamard transform of a class of generalized Carlet’s construction is calculated.

The rest of this paper is organized as follows. Section Ⅱ, we give a necessary and sufficient condition such that the quadratic Boolean function defined as Eq.(2) is bent-negabent. Section Ⅲ, we first present a new characterization of negabent functions. Further, a generalized nega-convolution theorem and the composition nega-Hadamard transform are presented and the nega-Hadamard transform of a class of generalized Carlet’s construction is calculated. Section Ⅳ gives some conclusions.

II.   A Class of Quadratic Bent-Negabent Functions

In this section, we will give a necessary and sufficient condition for a class of quadratic Boolean functions to be bent-negabent. First of all, let us recall a characterization of bent-negabent functions as follows.

Lemma 1^[10] The function $f: \mathbb{F}_{2^{n}}\rightarrow \mathbb{F}_{2}$ is negabent if and only if

It is known that the function $f: \mathbb{F}_{2^{n}}\rightarrow \mathbb{F}_{2}$ is bent if and only if

A function for which both Eqs.(3) and (4) hold is a bent-negabent function.

Similar to the method proposed in Ref.[11], we prove that the function $f$ defined in Eq.(2) is a negabent function.

Theorem 1 Let $f$ be the same those in Eq.(2). Then $f$ is negabent if and only if

is a linearized permutation polynomial, that is, $L(a)=0$ only has a solution 0.

Proof Since ${\rm{Tr}}_{\frac{n}{2}}^{n}(\cdot)$ is a surjective mapping from $\mathbb{F}_{2^{n}}$ to $\mathbb{F}_{2^{\frac{n}{2}}}$, there exists $c^{'}_{\frac{n}{2}} \in \mathbb{F}_{2^{n}}$ satisfying $c_{\frac{n}{2}} = {\rm{Tr}}_{\frac{n}{2}}^{n}(c^{'}_{\frac{n}{2}}) = c^{'}_{\frac{n}{2}}+c^{'\frac{n}{2}}_{\frac{n}{2}}$. For $f$ defined as in Eq.(2), we only need to prove that for all $a\in \mathbb{F}_{2^{n}}^{\ast}$

from Lemma 1. For simplicity, we denote

It follows from the properties of trace functions that

Then one can easily see that

hold if and only if $\sum_{i=1}^{\frac{n}{2}-1}(c_{i}a^{2^{i}} + c_{i}^{2^{n-i}}a^{2^{n-i}}) + c_{\frac{n}{2}}a^{2^{\frac{n}{2}}} + a\neq0$ for all $a\in \mathbb{F}_{2^{n}}^{\ast}$. It means that for such $c_{i}\in \mathbb{F}_{2^{n}}^{\ast}$ and $c_{\frac{n}{2}}\in \mathbb{F}_{2^{\frac{n}{2}}}$, the polynomial

has no nonzero root in $\mathbb{F}_{2^{n}}$. Note that $L(a)$ is a linearized polynomial and linearized polynomial is permutation if it has no nonzero root. The proof is then completed.

From Theorem 1, we have the following result immediately.

Theorem 2 Let $f$ be as in Eq.(2). Then $f$ is bent-negabent if and only if

is a complete mapping polynomial.

Proof From the proof of Theorem 1, we denote $L(a)$ as

From the result in Ref.[11] we know that $L_{f}(a)$ is a linearized permutation polynomial and Theorem 1 indicates that $L(a)$ is also a linearized permutation polynomial. Thus, $L_{f}(a)$ is a complete mapping polynomial from the definition of complete mapping polynomial^[13]. The proof is thus finished.

III.   Some Results on Convolution and Composition Theorems

1   A characterization of negabent functions

In this section, we present the characterization of negabent functions, by dividing the vector $x\in \mathbb{F}_{2}^{n}$ into the even weight ${\rm{E}}_{n}$ and the odd weight ${\rm{O}}_{n}$. Firstly, we will employ Jacobi’s two-square theorem as a lemma, which will be used to the proof of Theorem 3.

Lemma 2 Let $n$ be a non-negative integer. Then the integer solutions of the Diophantine equation $R^{2}+I^{2}=2^{n}$ are:

1) If $n$ is even, $(R,I)=(0,\pm2^{\frac{n}{2}})$ or $(\pm2^{\frac{n}{2}},0)$;

2) If $n$ is odd, $(R,I)=(\pm2^{\frac{n-1}{2}},\pm2^{\frac{n-1}{2}})$.

In the following, we give a new characterization of negabent functions.

Theorem 3 Let ${\rm{E}}_{n}$ and ${\rm{O}}_{n}$ be the set of vectors of even weight and odd weight over $\mathbb{F}_{2}^{n}$, respectively. Then the Boolean function $f\in {\cal{B}}_{n}$ is negabent if and only if

where

Proof By dividing the vector $x\in \mathbb{F}_{2}^{n}$, we have the even weight vectors set ${\rm{E}}_{n}$ and the odd weight vectors set ${\rm{O}}_{n}$. We denote

The nega-Hadamard transform of $f\in {\cal{B}}_{n}$ at $a\in \mathbb{F}_{2}^{n}$ can be represented as

where ${\bf 1}_{n}\cdot x=x_{1}+x_{2}+\cdots+x_{n}\in\{0,1\}.$

It follows from Eq.(5) that $f\in {\cal{B}}_{n}$ is negabent if and only if ${\rm{X}}_{e}^{2}+{\rm{X}}_{o}^{2}=2^{n}.$ By using Lemma 2, if $n$ is even, we have

and if $n$ is odd, we have $({\rm{X}}_{e},{\rm{X}}_{o})=(\pm2^{\frac{n-1}{2}},\pm2^{\frac{n-1}{2}})$. The theorem follows.

By Theorem 3, we reprove the Lemma 1 of Ref.[14] by a simpler method.

Proposition 1 Let $f\in {\cal{B}}_{n}$. The relation between the nega-Hadamard transform of $f$ and the Walsh-Hadamard transform of $f$ can be described as

Proof Let $a=(a_{1},\ldots,a_{n})\in \mathbb{F}_{2}^{n}$. Then $\overline{a}=a+ {\bf 1}_{n}$ denotes the bitwise complement of $a$. Thus, the nega-Hadamard transform of $f$ at $a\in \mathbb{F}_{2}^{n}$ is

The proposition follows.

2   Generalized nega-convolution and composition theorem for (vectorial) Boolean functions

In the following, we further describe the generalized nega-convolution theorem. Let $h\in {\cal{B}}_{n}$ be a $n$-variable Boolean function and satisfy $h(x)=f(x)+ g(x)$, where $f,g\in {\cal{B}}_{n}$. Then the Walsh-convolution transform of function $h$ is given by

A general result of Walsh-convolution transform theorem has been given in Ref.[12].

Inspired by Ref.[12], we have the following theorem.

Theorem 4 Let $f_{1}(x),\ldots,f_{k}(x)\in {\cal{B}} _{n}$ and $h(x)=f_{1}(x)+ \cdots+ f_{k}(x)$. Then the generalized nega-convolution of $h$ at $u\in \mathbb{F}_{2}^{n}$ is given by

where $m=(k-1)n$, $v=(v_{1},\ldots,v_{k-1})$, $v_{k}=u$ with each $v_{i}\in \mathbb{F}_{2}^{n}$. In particular, if $k=2$, then ${\cal{N}}_{h}(u)=$ $2^{-\frac{n}{2}}\sum_{v\in \mathbb{F}_{2}^{n}}{\cal{N}}_{f}(v){\cal{W}}_{g}(u+ v)$.

Proof We show Eq.(6) by inducting on $k$. For $k=2$, the result is obvious. Assume that result holds for $k-1\geq2$. We now apply the nega-convolution theorem on the $f_{k}(x)$ and $f(x)=f_{1}(x)+ \cdots+ f_{k-1}(x)$. We obtain

Now we invoke the induction hypothesis for $k-1$ on the function $f$ to get

The theorem follows.

The mappings from $\mathbb{F}_{2}^{n}$ to $\mathbb{F}_{2}^{m}$ are called $(n,m)$-functions (or vectorial functions), where $n,m\in \mathbb{Z^{+}}$. Let $G : \mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}^{m}$ be a vectorial Boolean function and $K : \mathbb{F}_{2}^{m}\rightarrow \mathbb{F}_{2}$ be an $m$-variable Boolean function defined by $(K\circ G)(x)=K(G(x))$. Now we provide the nega-Hadamard transform of composition of a Boolean function and a vectorial Boolean function.

Theorem 5 Let $G : \mathbb{F}_{2}^{n}\rightarrow \mathbb{F}_{2}^{m}$ and $K : \mathbb{F}_{2}^{m}\rightarrow \mathbb{F}_{2}$. Then the generalized composition theorem of $G$ and $K$ at any $u\in \mathbb{F}_{2}^{n}, v\in\mathbb{F}_{2}^{m}$ is given by

where $L_{v}(x)=v\cdot x$ is a linear function and $(L_{v}\circ G)(x)= v\cdot G(x)$.

Proof It follows from the inverse Walsh-Hadamard transform that

Let $y=G(x)$. Then

Therefore

The theorem follows.

Theorem 5 provides a new method to derive the nega-Hadamard transform of secondary construction.

In the following, we present the nega-Hadamard transform of the Boolean function $h(x,y)=f(x)g(y)$ by using the generalized composition method of Theorem 5. Also, in order to prove Theorem 6, we shall make use of the following lemma.

Lemma 3^[15] For any $u\in \mathbb{F}_{2}^{n}$, we have

where $\omega=\frac{1}{\sqrt{2}}(1+i)$ is a 8th primitive root of unity.

Theorem 6 If $f(x)\in {\cal{B}}_{n}$, $g(y)\in {\cal{B}}_{m}$ and $h(x,y)=f(x)g(y)$, then the nega-Hadamard transform of $h$ at $u\in \mathbb{F}_{2}^{n}$, $v\in \mathbb{F}_{2}^{m}$ is given by

where $\omega=\frac{1}{\sqrt{2}}(1+i)$ is a primitive 8th root of unity.

Proof Let $K(x_{1}, x_{2})=x_{1}x_{2}$. Then ${\cal{W}}_{K}=\pm1$ and its support is $\mathbb{F}_{2}^{2}$. Since $G=K(f,g)$, according to Eq.(7) of Theorem 5 and Lemma 3, we have

The theorem follows.

Remark 2 In Ref.[8], with the same notation as in Theorem 6, it is proved that

where $A_{g_{1}}(v)+A_{g_{0}}(v)=2^{\frac{m}{2}}\omega^{m}i^{-wt(v)}$, $A_{g_{0}}(v)=$ $\sum_{y, g(y)=0}(-1)^{y\cdot v}i^{wt(y)}$, $A_{g_{1}}(v)=\sum_{y, g(y)=1}(-1)^{y\cdot v}i^{wt(y)}$. Now, we further evaluate $A_{g_{0}}(v)$, $A_{g_{1}}(v)$ from Lemma 3 as follows

Thus, the right of Eq.(9) can be rewritten as

It means that the result in Eq.(9) is equal to Eq.(8).

3   The nega-Hadamard transform of a class of generalized Carlet’s construction

The secondary construction is an efficient way to generate more Boolean (or bent) functions^{[1, 16, 17]}. An important secondary construction of bent functions is the classical Carlet’s construction (or called the indirect sum)^[16] which defined as

and a class of the generalized indirect sum defined as

which was introduced by Ref.[17]. In the following, based on the generalized composition theorem, the nega-Hadamard transform of this generalized indirect sum can be obtained easily.

Theorem 7 Let $f_{1}, f_{2}, f_{3}\in {\cal{B}}_{n}$ and $g_{1}, g_{2}, g_{3}\in {\cal{B}}_{m}$. Let function $h(x,y)\in{\cal{B}}_{n+m}$ be defined as in Eq.(10). Then the nega-Hadamard transform of $h(x,y)$ at any $(u,v)\in \mathbb{F}_{2}^{n}\times \mathbb{F}_{2}^{m}$ is given by

Proof Let

Then we have $G=K(f_{1}, f_{2}, f_{3}, g_{1}, g_{2}, g_{3})$. By the straight computation, we present the nonzero Walsh-Hadamard transforms of $K$ is

From Eq.(7) of Theorem 5, we can obtain

The theorem follows.

By Theorem 7, a sufficient condition for function $h$ as in Eq.(10) to be negabent can be given.

Theorem 8 Let $n$ and $m$ be two positive integers. Let $f_{1},\; f_{2},\; f_{3}$ and $f_{1}+ f_{2}+ f_{3}$ be negabent functions in $n$ variables. Let $g_{1},\; g_{2},\; g_{3}$ and $g_{1}+ g_{2}+ g_{3}$ be negabent functions in $m$ variables, and if $\frac{{\cal{N}}_{g_{1}}(v)}{{\cal{N}}_{g_{2}}(v)}=\pm1$, $\frac{{\cal{N}}_{g_{2}}(v)}{{\cal{N}}_{g_{3}}(v)}=\pm1$, $\frac{{\cal{N}}_{g_{3}}(v)}{{\cal{N}}_{g_{1}}(v)}=\pm1$, $\frac{{\cal{N}}_{g_{1}}(v)}{{\cal{N}}_{g_{1}+ g_{2}+ g_{3}}(v)}= \pm1$, $\frac{{\cal{N}}_{g_{2}}(v)}{{\cal{N}}_{g_{1}+ g_{2}+ g_{3}}(v)}=\pm1$, and $\frac{{\cal{N}}_{g_{3}}(v)}{{\cal{N}}_{g_{1}+ g_{2}+ g_{3}}(v)}=\pm1$, for all $(u,v)\in \mathbb{F}_{2}^{n}\times \mathbb{F}_{2}^{m}$. Then the function defined as in Eq.(10) is a negabent function in $n+m$ variables.

Proof For simplicity, set $z={\cal{N}}_{h}(u,v)$, $z_{1} ={\cal{N}}_{f_{1}}(u)$, $z_{2}={\cal{N}}_{f_{2}}(u)$, $z_{3}={\cal{N}}_{f_{3}}(u)$, $z_{4}={\cal{N}}_{g_{1}}(v)$, $z_{5}={\cal{N}}_{g_{2}}(v)$, $z_{6}={\cal{N}}_{g_{3}}(v)$, $z_{7}={\cal{N}}_{f_{1}+ f_{2}+ f_{3}}(u)$, $z_{8}={\cal{N}}_{f_{1}+ f_{2}+ f_{3}}(v)$. By Theorem 7, for all $(u,v)\in \mathbb{F}_{2}^{n}\times \mathbb{F}_{2}^{m}$, we have

and

Combining Eqs.(11) and (12), since $|\bar{z_{1}}|=|\bar{z_{2}}|= |\bar{z_{3}}|=|\bar{z_{7}}|=1$, $|\bar{z_{4}}|=|\bar{z_{5}}|=|\bar{z_{6}}|=|\bar{z_{8}}|=1$, and $\frac{z_{4}}{z_{5}}=\pm1$, $\frac{z_{4}}{z_{6}}=\pm1$, $\frac{z_{4}}{z_{8}}=\pm1$, $\frac{z_{5}}{z_{6}}=\pm1$, $\frac{z_{5}}{z_{8}}=\pm1$, $\frac{z_{6}}{z_{8}}=\pm1$, we have $16|z|^{2} =16$, which implies that $|z|^{2}=1$. Therefore, we have $|{\cal{N}}_{h}(u,v)|=1$, that is the function defined as in Eq.(10) is a negabent function in $n+m$ variables. The theorem follows.

If $f_{2}=f_{3}$ or $g_{2}=g_{3}$ in Theorem 7, the following corollary is obvious.

Corollary 1 Let the notations be same as in Theorem 7. If $f_{2} = f_{3}$ or $g_{2}=g_{3}$, then we have

The necessary and sufficient condition that $h(x, y)$ defined in Corollary 1 is bent-negabent has been proposed in Ref.[18].

IV.   Conclusions

In this paper, we have provided a necessary and sufficient condition for a class of quadratic Boolean functions to be bent-negabent, and presented another characterization of negabent functions. Furthermore, we give the generalized nega-convolution theorem, and present the composition nega-Hadamard transform for a Boolean function and a vectorial Boolean function. It would be interesting to study more efficient constructions using this composition method.