Paper 2016/1078

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

Deng Tang and Subhamoy Maitra

Abstract

In this paper we consider the maximum absolute value $\Delta_f$ in the autocorrelation spectrum (not considering the zero point) of a function $f$. In even number of variables $n$, bent functions possess the highest nonlinearity with $\Delta_f = 0$. The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with $\Delta_f < 2^{\frac n2}$. So far there are only a few examples of such functions for $n = 10, 14$, but no general construction technique is known. In this paper, we mathematically construct an infinite class of balanced Boolean functions on $n$ variables having absolute indicator strictly lesser than $\delta_n = 2^{\frac{n}{2}}-2^{\frac{n+6}{4}}$, nonlinearity strictly greater than $\rho_n = 2^{n-1} - 2^{\frac{n}{2}} + 2^{\frac n2-3} - 5\cdot2^{\frac{n-2}{4}}$ and algebraic degree $n-1$, where $n\equiv 2 \pmod 4$ and $n\geq 46$. While the bound $n \geq 46$ is required for proving the generic result, our construction starts from $n = 18$ and we could obtain balanced functions with $\Delta_f < 2^{\frac{n}{2}}$ and nonlinearity $> 2^{n-1} - 2^\frac{n}{2}$ for $n = 18, 22$ and $26$.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Absolute IndicatorAutocorrelation SpectrumBalancednessBoolean functionNonlinearity.
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/1078}},
      url = {https://eprint.iacr.org/2016/1078}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.