New Patterson-Wiedemann type functions with 15 variables in the generalized rotation-symmetric class


Abstract: Recently, it was shown that there is no Boolean function on 15 variables with nonlinearity greater than 16276 in the class of functions that are invariant under the action of GF(2$^{3})^{\ast }\times GF(2^{5})^{\ast }$. In this study, we consider some important subsets of this class and perform an efficient enumeration of the 15-variable Patterson-Wiedemann (PW) type functions with nonlinearity greater than the bent concatenation bound 16256 in the generalized classes of both 3-RSBFs and 5-RSBFs for which the corresponding search spaces are 2$^{28.2}$ and 2$^{47.85}$, respectively. For the case of 3-RSBFs, we find that there are 32 functions with nonlinearity $>$ 16256, such that 8 of them correspond to the original PW constructions, while the remaining 24 functions are new in the sense that they are not affine equivalent to the known ones. For the other case of 5-RSBFs, our results show that there are 478 functions with nonlinearity exceeding the bent concatenation bound, among which there is another set of 470 functions that are affine inequivalent to the known PW constructions.

Keywords: Nonlinearity, Boolean functions, Patterson-Wiedemann type functions

Full Text: PDF