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

Kavut S., DİKER M.

INFORMATION AND COMPUTATION, cilt.208, sa.4, ss.341-350, 2010 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 208 Sayı: 4
  • Basım Tarihi: 2010
  • Doi Numarası: 10.1016/j.ic.2009.12.002
  • Dergi Adı: INFORMATION AND COMPUTATION
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.341-350
  • Anahtar Kelimeler: Boolean functions, Combinatorial problems, Cryptography, Dihedral symmetry, Nonlinearity, Rotational symmetry, REED-MULLER CODE, COVERING RADIUS, COSETS, BENT
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.