Negabent Functions in the Maiorana–McFarland Class - Sequences and Their Applications-SETA 2008 - page 390

Negabent Functions
in the Maiorana-McFarland Class

Kai-Uwe Schmidt 1 , Matthew G. Parker 2 , and Alexander Pott 3

1 Department of Mathematics, Simon Fraser University
Burnaby, BC V5A 1S6, Canada
[e-mail]
2 The Selmer Center, Department of Informatics, University of Bergen
N-5020 Bergen, Norway
[e-mail]
3 Institute for Algebra and Geometry, Faculty of Mathematics,
Otto-von-Guericke-University Magdeburg,
D-39016 Magdeburg, Germany
[e-mail]

Abstract. Boolean functions which are simultaneously bent and ne-
gabent are studied. Transformations that leave the bent-negabent
property invariant are presented. A construction for infinitely many bent-
negabent Boolean functions in 2 mn variables ( m> 1) and of algebraic
degree at most n is described, this being a subclass of the Maiorana-
McFarland class of bent functions. Finally it is shown that a bent-
negabent function in 2 n variables from the Maiorona-McFarland class
has algebraic degree at most n − 1.

1 Introduction

Bent Boolean functions are the class of Boolean functions whose spectral values
have equal magnitude with respect to the Hadamard transform [1]. The con-
struction and classification of bent functions is of significant and active interest
to designers of cryptographic primitives [2], as such functions have maximum
distance to the set of ane functions and, therefore, are not well-approximated
by ane functions. It is natural also to consider spectral values with respect to
the nega-Hadamard transform . If these spectral values of a Boolean function are
all equal in magnitude, then we call the function negabent .
In this paper we consider how to construct Boolean functions that are simul-
taneously bent and negabent. Such a problem has been previously considered
in [3], providing constructions for quadratic functions. Here we present a new
and infinite construction for functions of more general algebraic degree, thereby
answering and generalizing a conjecture made in [3]. More precisely, we con-
struct a subclass of the Maiorana-McFarland class of bent functions in which
all functions are also negabent. This construction generalizes the construction
of quadratic bent-negabent functions described in [4, 5]. These functions are in
2 mn variables and have algebraic degree at most n ,where m> 1.