Decomposing Bent Function
Anne Canteaut and Pascale Charpin
INRIA, projet CODES
78153 Le Chesnay Cedex, France
Regular paper in IEEE Trans. Inform. Theory , 49(8), August 2003.
presented at ISIT 2002, Lausanne, Switzerland.
In a recent paper, it is shown that the
restrictions of bent functions to subspaces
of codimension 1 and 2 are highly nonlinear.
Here, we present an extensive study of the restrictions
of bent functions to affine subspaces. We propose several methods
which are mainly based on properties of
the derivatives and of the dual of a given bent function.
We solve an open problem due to Hou (1990).
We especially describe the connection, for a bent function,
between the Fourier spectra of its restrictions and
the decompositions of its dual. Most notably, we show that the Fourier
spectra of the restrictions of a bent function to the subspaces of
codimension 2 can be explicitly derived from the Hamming weights of
the second derivatives of the dual function. The last part of the paper
is devoted to some infinite classes of bent functions which cannot be
decomposed into four bent functions.
Bent functions, Boolean functions,
derivatives of Boolean functions, Reed-Muller codes, restrictions of