2008/08/05 by Selçuk Kavut, Selcuk Kavut, Kavut, Selcuk +3
Computer Science · Engineering · Mathematics · Medicine · #Cancer Mechanisms and Therapy #Coding theory and cryptography #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.CR #cs.IT #graph theory and CDMA systems #math.IT
paper · pdf · doi:10.48550/arxiv.0808.0684
This work is based on (i) "Generalized Rotation Symmetric and Dihedral Symmetric Boolean Functions - 9 variable Boolean Functions with Nonlinearity 242", AAECC-17 Symposium, LNCS Vol. 4851, pp. 321-329, Bangalore, India, 2007 and (ii) "Random Permutations on Input Vectors of Boolean Functions", BFCA 2008, Copenhagen, Denmark, 2008
arxiv created 2008/08/05 · openalex publication_date 2008/08/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.