Normal Boolean functions
INRIA, projet CODES
78153 Le Chesnay Cedex, France
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.
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
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.
Boolean function, nonlinearity, bent function,
almost optimal function, resilient function, normality,