Cryptology ePrint Archive: Report 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\c{c}uk Kavut and Subhamoy Maitra and Melek D. Y{\"u}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 $< 2^{\frac{n}{2}}$, 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.

Category / Keywords: foundations / Boolean Functions, Nonlinearity

Date: received 28 May 2006, last revised 19 Jul 2006

Contact author: subho at isical ac in

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

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.

Version: 20060719:100142 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]