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 $< 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.

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.

Metadata
Available format(s)
PDF PS
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Boolean FunctionsNonlinearity
Contact author(s)
subho @ isical ac in
History
2006-07-19: last of 3 revisions
2006-05-30: received
See all versions
Short URL
https://ia.cr/2006/181
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2006/181,
      author = {Selçuk Kavut and Subhamoy Maitra and Melek D.  Yücel},
      title = {There exist Boolean functions on $n$ (odd) variables having nonlinearity $> 2^{n-1} - 2^{\frac{n-1}{2}}$ if and only if $n > 7$},
      howpublished = {Cryptology ePrint Archive, Paper 2006/181},
      year = {2006},
      note = {\url{https://eprint.iacr.org/2006/181}},
      url = {https://eprint.iacr.org/2006/181}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.