9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class

AbstractWe give a new lower bound to the covering radius of the first order Reed–Muller code RM(1,n), where n∈{9,11,13}. Equivalently, we present the n-variable Boolean functions for n∈{9,11,13} with maximum nonlinearity found till now. 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 Yücel. 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. Secondly, utilizing a steepest-descent like iterative heuristic search algorithm, we have found 9-variable Boolean functions with nonlinearity 242 within the classes of both 3-RSBFs and 3-DSBFs. 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