Paper 2006/181

There exist Boolean functions on $n$ (odd) variables having nonlinearity $>2^{n-1}-2^{\frac{n-1}{2}}$ if and only if $n>7$

Selçuk Kavut, Subhamoy Maitra, and Melek D. Yücel

Abstract

For the first time we find Boolean functions on 9 variables having nonlinearity 241, that remained as an open question in literature for almost three decades. Such functions are discovered using a suitably modified steepest-descent based iterative heuristic search in the class of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on $n$ (odd) variables having nonlinearity $>2^{n-1}-2^{\frac{n-1}{2}}$ if and only if $n>7$. Using the same search method, we also find several other important functions and we study the autocorrelation, propagation characteristics and resiliency of the RSBFs (using proper affine transformations, if required). The results show that it is possible to get balanced Boolean functions on $n=10$ variables having autocorrelation spectra with maximum absolute value $$, which was not known earlier. In certain cases the functions can be affinely transformed to get first order propagation characteristics. We also obtain 10-variable functions having first order resiliency and nonlinearity 492 which was posed as an open question in Crypto 2000.

Note: The initial draft was to quickly announce the finding of 9-variable Boolean functions with nonlinearity 241. This current revision contains a detailed description of the search method and also reports several other important functions.