Search for Boolean functions with excellent profiles in the rotation symmetric class

Date

2007-05-01

Author

Kavut, Selcuk
Maitra, Subhamoy
Yucel, Melek D.

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

8
views

0
downloads

Cite This

For the first time Boolean functions on 9 variables having nonlinearity 241 are discovered, that remained as an open question in literature for almost three decades. Such functions are found by heuristic search in the space of rotation symmetric Boolean functions (RSBFs). This shows that there exist Boolean functions on n (odd) variables having non, linearity > 2(n-1) - 2 (n-1/2) if and only if n > 7. Using similar search technique, balanced Boolean functions on 9, 10, and 11 variables are attained having autocorrelation spectra with maximum absolute value < 2 [n/2]. On odd number of variables, earlier such functions were known for 15, 21 variables; there was no evidence of such functions at all on even number of variables. In certain cases, our functions can be affinely transformed to obtain first-order resiliency or first-order propagation characteristics. Moreover, 10 variable functions having first-order resiliency and nonlinearity 492 are presented that had been posed as an open question at Crypto 2000. The functions reported in this paper are discovered using a suitably modified steepest descent based iterative heuristic search in the RSBF class along with proper affine transformations. It seems elusive to get a construction technique to match such functions.

Subject Keywords

Library and Information Sciences, Information Systems, Computer Science Applications

URI

https://hdl.handle.net/11511/67303

Collections

Department of Electrical and Electronics Engineering, Article