A Note on Generalized Bent Criteria for Boolean Functions

Abstract

In this paper, we consider the spectra of Boolean functions with respect to the action of unitary transforms obtained by taking tensor products of the Hadamard kernel, denoted by <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</i> , and the nega-Hadamard kernel, denoted by <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> . The set of all such transforms is denoted by { <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</i> , <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> } <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> . A Boolean function is said to be bent <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sub> if its spectrum with respect to at least one unitary transform in { <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">H</i> , <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</i> } <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> is flat. We obtain a relationship between bent, semibent, and bent <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sub> functions, which is a generalization of the relationship between bent and negabent Boolean functions proved by Parker and Pott [cf., LNCS 4893 (2007), 9-23]. As a corollary to this result, we prove that the maximum possible algebraic degree of a bent <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sub> function on <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> variables is [ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> /2] and, hence, solve an open problem posed by Riera and Parker [cf., IEEE-TIT 52:9 (2006), 4142-4159].