  In 2006, 9-variable Boolean functions having nonlinearity 241, which is
strictly greater than the bent concatenation bound of 240, have been discovered
in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra
and Yucel. To improve this nonlinearity result, we have firstly defined some
subsets of the n-variable Boolean functions as the "generalized classes of
k-RSBFs and k-DSBFs (k-Dihedral Symmetric Boolean Functions)", where k is a
positive integer dividing n and k-RSBFs is a subset of l-RSBFs if k < l.
Secondly, utilizing the steepest-descent like iterative heuristic search
algorithm used previously to identify the 9-variable RSBFs with nonlinearity
241, we have made a search within the classes of 3-RSBFs and 3-DSBFs. The
search has accomplished to find 9-variable Boolean functions with nonlinearity
242 in both of these classes. It should be emphasized that although the class
of 3-RSBFs contains functions with nonlinearity 242; 1-RSBFs or simply RSBFs,
which is a subset of 3-RSBFs, does not contain any. This result also shows that
the covering radius of the first order Reed-Muller code R(1, 9) is at least
equal to 242. Thirdly, motivated by the fact that RSBFs are invariant under a
special permutation of the input vector, we have classified all possible
permutations up to the linear equivalence of Boolean functions that are
invariant under those permutations. Specifically, for 9-variable Boolean
functions, 9! possible permutations are classified into 30 classes; and the
search algorithm identifies some of these classes as "rich". The rich classes
yield new Boolean functions with nonlinearity 242 having different
autocorrelation spectra from those of the functions found in the generalized
3-RSBF and 3-DSBF classes.
