Welcome to the resource topic for 2006/181
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
Authors: Selçuk Kavut, Subhamoy Maitra, 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.
ePrint: https://eprint.iacr.org/2006/181
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .