Balanced Boolean Functions with Nonlinearity > 2^{n-1} - 2^{(n-1)/2}

Selcuk Kavut; Melek Diker Yucel

Paper 2007/321

Balanced Boolean Functions with Nonlinearity > 2^{n-1} - 2^{(n-1)/2}

Selcuk Kavut and Melek Diker Yucel

Abstract

Recently, balanced 15-variable Boolean functions with nonlinearity 16266 were obtained by suitably modifying unbalanced Patterson-Wiedemann (PW) functions, which possess nonlinearity 2^{n-1}-2^{(n-1)/2}+20 = 16276. In this short paper, we present an idempotent interpreted as rotation symmetric Boolean function) with nonlinearity 16268 having 15 many zeroes in the Walsh spectrum, within the neighborhood of PW functions. Clearly this function can be transformed to balanced functions keeping the nonlinearity and autocorrelation distribution unchanged. The nonlinearity value of 16268 is currently the best known for balanced 15-variable Boolean functions. Furthermore, we have attained several balanced 13-variable Boolean functions with nonlinearity 4036, which improves the recent result of 4034.

Note: The result of balanced 13-variable Boolean functions with nonlinearity 4036 is added.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Balanced Boolean functions Nonlinearity
Contact author(s): selcukkavut @ gmail com
History: 2007-09-07: last of 4 revisions; 2007-08-16: received; See all versions
Short URL: https://ia.cr/2007/321
License: CC BY

BibTeX

@misc{cryptoeprint:2007/321,
      author = {Selcuk Kavut and Melek Diker Yucel},
      title = {Balanced Boolean Functions with Nonlinearity > 2^{n-1} - 2^{(n-1)/2}},
      howpublished = {Cryptology ePrint Archive, Paper 2007/321},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/321}},
      url = {https://eprint.iacr.org/2007/321}
}