Investigations on Bent and Negabent Functions via the Nega-Hadamard Transform

Abstract

Parker <etal xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"/> considered a new type of discrete Fourier transform, called nega-Hadamard transform. We prove several results regarding its behavior on combinations of Boolean functions and use this theory to derive several results on negabentness (that is, flat nega-spectrum) of concatenations, and partially symmetric functions. We derive the upper bound <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$\lceil {{ n}\over { 2}} \rceil $</tex></formula> for the algebraic degree of a negabent function on <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex Notation="TeX">$n$</tex></formula> variables. Further, a characterization of bent–negabent functions is obtained within a subclass of the Maiorana–McFarland set. We develop a technique to construct bent–negabent Boolean functions by using complete mapping polynomials. Using this technique, we demonstrate that for each <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\ell \geq 2$</tex></formula> , there exist bent–negabent functions on <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$n = 12\ell $</tex></formula> variables with algebraic degree <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$ {{ n}\over { 4}}+1 = 3\ell + 1$</tex></formula> . It is also demonstrated that there exist bent–negabent functions on eight variables with algebraic degrees 2, 3, and 4. Simple proofs of several previously known facts are obtained as immediate consequences of our work.