[Resource Topic] 2016/1078: Construction of $n$-variable ($n\equiv 2 \bmod 4$) balanced Boolean functions with maximum absolute value in autocorrelation spectra $< 2^{\frac n2}$

Welcome to the resource topic for 2016/1078

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

Authors: Deng Tang, 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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.