Construction of $n$-variable ($n\equiv 2 \bmod 4$) balanced Boolean functions with maximum absolute value in autocorrelation spectra $< 2^{\frac n2}$

Deng Tang; Subhamoy Maitra

Paper 2016/1078

Construction of -variable () balanced Boolean functions with maximum absolute value in autocorrelation spectra

Deng Tang and Subhamoy Maitra

Abstract

In this paper we consider the maximum absolute value in the autocorrelation spectrum (not considering the zero point) of a function . In even number of variables , bent functions possess the highest nonlinearity with . The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with . So far there are only a few examples of such functions for , but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on variables having absolute indicator strictly lesser than , nonlinearity strictly greater than and algebraic degree , where and . While the bound is required for proving the generic result, our construction starts from and we could obtain balanced functions with and nonlinearity for and .

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: Absolute Indicator Autocorrelation Spectrum Balancedness Boolean function Nonlinearity.
Contact author(s): subho @ isical ac in
History: 2016-11-21: revised; 2016-11-21: received; See all versions
Short URL: https://ia.cr/2016/1078
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1078,
      author = {Deng Tang and Subhamoy Maitra},
      title = {Construction of $n$-variable ($n\equiv 2 \bmod 4$) balanced Boolean functions with maximum absolute value in autocorrelation spectra $< 2^{\frac n2}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1078},
      year = {2016},
      url = {https://eprint.iacr.org/2016/1078}
}