Construction of $n$ -Variable ( $n\equiv 2 \bmod 4$ ) Balanced Boolean Functions With Maximum Absolute Value in Autocorrelation Spectra $
Deng Tang, Subhamoy Maitra · IEEE Transactions on Information Theory · 2017
In this paper, we consider the maximum absolute value Δfin the autocorrelation spectrum (not considering the zero point) of a function f. In an even number of variables n, bent functions possess the highest nonlinearity with Δf= 0. The long standing open question (for two decades) in this area is to obtain a theoretical construction of balanced functions with Δfn/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 δn= 2n/2- 2((n+6)/4), nonlinearity strictly greater than ρn= 2n-1-2n/2+2n/2-3-5·2((n-2)/4)and algebraic degree n - 1, where n ≡ 2 (mod 4) and n ≥ 46. While the bound n ≥ 46 is required for proving the generic result, our construction starts from n = 18, and we could obtain balanced functions with Δfn/2and nonlinearity > 2n-1- 2n/2for n = 18, 22, and 26.