On Boolean Functions Which Are Bent and Negabent
Bent functions \(f:\mathbb{F}_2^m\rightarrow \mathbb{F}_2\) achieve largest distance to all linear functions. Equivalently, their spectrum with respect to the Hadamard-Walsh transform is flat (i.e. all spectral values have the same absolute value). That i
- PDF / 472,019 Bytes
- 15 Pages / 430 x 660 pts Page_size
- 24 Downloads / 237 Views
The Selmer Center, Department of Informatics, University of Bergen, N-5020 Bergen, Norway 2 Institute for Algebra and Geometry, Faculty of Mathematics, Otto-von-Guericke-University Magdeburg, D-39016 Magdeburg, Germany
Abstract. Bent functions f : Fm 2 → F2 achieve largest distance to all linear functions. Equivalently, their spectrum with respect to the Hadamard-Walsh transform is flat (i.e. all spectral values have the same absolute value). That is equivalent to saying that the function f has optimum periodic autocorrelation properties. Negaperiodic correlation properties of f are related to another unitary transform called the negaHadamard transform. A function is called negabent if the spectrum under the nega-Hadamard transform is flat. In this paper, we consider functions f which are simultaneously bent and negabent, i.e. which have optimum periodic and negaperiodic properties. Several constructions and classifications are presented. Keywords: bent function, Boolean function, unitary transform, Hadamard-Walsh transform, correlation.
1
Introduction
Boolean functions f : Fm 2 → F2 play an important role in cryptography. They should satisfy several properties, which are quite often impossible to be satisfied simultaneously. One property is the nonlinearity of a Boolean function, which means that the function is as far away from all linear functions as possible. Functions which achieve this goal are called bent functions. Equivalently, all Hadamard-Walsh coefficients of f are equal in absolute value. There is another criteria which may be viewed as the negaperiodic analogue of the bent criteria. In spectral terms, it may be formulated as follows: Find functions whose nega-Hadamard spectrum is flat, i.e. all spectral values under the nega-Hadamard transform are equal in absolute value. Many bent functions are known, and also many negabent functions are known: It turns out that every linear function is negabent! In this paper, we are going to investigate the intersection of these two sets, i.e. we are searching for bent functions which are simultaneously negabent. At first view, it is not clear that such objects exist. An infinite series of bent-negabent functions has been found in [1,2]. We give necessary and sufficient conditions for quadratic functions to be both bent and negabent, which is based on [2]. It turns out that such quadratic bentnegabent functions exist for all even m, which generalizes the series in [2]. S.W. Golomb et al. (Eds.): SSC 2007, LNCS 4893, pp. 9–23, 2007. c Springer-Verlag Berlin Heidelberg 2007
10
M.G. Parker and A. Pott
More generally, we can describe all Maiorana-McFarland type bent functions which are simultaneously negabent. It seems to be difficult to exploit this condition in general. The concept of a dual bent function is well known. If f is bent-negabent, then the dual has the same property. There is another interesting transformation which turns a bent-negabent function into a bent-negabent function. We call this Schmidt complementation since it is based on a construction in [4]. T
Data Loading...
