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

Kavut S., DİKER M.

INFORMATION AND COMPUTATION, vol.208, no.4, pp.341-350, 2010 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 208 Issue: 4
  • Publication Date: 2010
  • Doi Number: 10.1016/j.ic.2009.12.002
  • Page Numbers: pp.341-350
  • Keywords: Boolean functions, Combinatorial problems, Cryptography, Dihedral symmetry, Nonlinearity, Rotational symmetry, REED-MULLER CODE, COVERING RADIUS, COSETS, BENT


We give a new lower bound to the covering radius of the first order Reed-Muller code RM(1, n), where n is an element of {9, 11, 13}. Equivalently, we present the n-variable Boolean functions for n is an element of {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 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. 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. (C) 2009 Elsevier Inc. All rights reserved.