Normal Boolean functions


Pascale Charpin

INRIA, projet CODES
BP 105
78153 Le Chesnay Cedex, France
Pascale.Charpin@inria.fr

Special Issue "Complexity Issues in Cryptography and Coding Theory",
dedicated to Prof. Harald Niederreiter on the occasion of his 60th birthday.
Journal of Complexity , 20(2004) 245-265.


Abstract

In 1995, Dobbertin introduced the normality of bent functions. His work strengthened the interest for the study of the restrictions of Boolean functions on k-dimensional flats providing the concept of k-normality. Using recent results on the decomposition of any Boolean functions with respect to some subspace, we present several formulation of k-normality. We later focus on some highly linear functions, bent functions and almost optimal functions. We point out that normality is a property for which these two classes are strongly connected. We propose several improvements for checking normality, again based on specific decompositions introduced in our recent papers. As an illustration, we show that cubic bent functions of 8 variables are normal.

Keywords

Boolean function, nonlinearity, bent function, almost optimal function, resilient function, normality, k-normality.