International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Balanced Boolean Function on 13-variables having Nonlinearity strictly greater than the Bent Concatenation Bound

Authors:
Subhamoy Maitra
Download:
URL: http://eprint.iacr.org/2007/309
Search ePrint
Search Google
Abstract: Very recently, Kavut and Yucel identified 9-variable Boolean functions having nonlinearity 242, which is currently the best known. However, any of these functions do not contain any zero in the Walsh spectrum and that is why they cannot be made balanced. We use these functions to construct 13-variable balanced Boolean function having nonlinearity $2^{13-1} - 2^{\frac{13-1}{2}} + 2 = 4034$ which is strictly greater than the bent concatenation bound. This is the first demonstration of balanced Boolean functions on odd number of variables having nonlinearity strictly greater than the bent concatenation bound for number of input variables less than 15.
BibTeX
@misc{eprint-2007-13589,
  title={Balanced Boolean Function on 13-variables having Nonlinearity strictly greater than the Bent Concatenation Bound},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Balancedness, Boolean Function, Nonlinearity.},
  url={http://eprint.iacr.org/2007/309},
  note={ subho@isical.ac.in 13752 received 10 Aug 2007, last revised 27 Aug 2007},
  author={Subhamoy Maitra},
  year=2007
}