**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$.

**Category / Keywords: **secret-key cryptography / Absolute Indicator, Autocorrelation Spectrum, Balancedness, Boolean function, Nonlinearity.

**Date: **received 17 Nov 2016, last revised 21 Nov 2016

**Contact author: **subho at isical ac in

**Available format(s): **PDF | BibTeX Citation

**Version: **20161121:124927 (All versions of this report)

**Short URL: **ia.cr/2016/1078

[ Cryptology ePrint archive ]