Paper 2016/1078

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

Deng Tang and Subhamoy Maitra

Abstract

In this paper we consider the maximum absolute value ${\mathrm{\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 ${\mathrm{\Delta }}_f=0$. The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with ${\mathrm{\Delta }}_f<2^{\frac{n}{2}}$. 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{n}{2}-3}-5\cdot 2^{\frac{n-2}{4}}$ and algebraic degree $n-1$, where $n\equiv 2(\mathrm{mod}4)$ and $n\ge 46$. While the bound $n\ge 46$ is required for proving the generic result, our construction starts from $n=18$ and we could obtain balanced functions with $$ and nonlinearity $$ for $$ and $$.