Construction of bent functions from near-bent functions (Q1024350)

A function \(f\) from an \(n\)-dimensional vector space \(V_n\) over \(\mathbb{F}_2\) into \(\mathbb{F}_2\) is called bent (near-bent) if its Walsh transform \(\hat{f}(u) = \sum_{x\in V_n}(-1)^{f(x)+\langle u,x\rangle}\) where \(\langle\;,\;\rangle\) denotes any inner product on \(V_n\) takes values in \(\{\pm 2^{n/2}\}\) (\(\{0,\pm 2^{(n+1)/2}\}\)) only. The authors suggest the construction of bent functions \(g(x,y) = yh(x)+(y+1)f(x)\) from \(V_n\times V_1\) into \(\mathbb{F}_2\) from two near-bent functions \(f,h\) on \(V_n\). A necessary and sufficient condition for \(g\) being bent is that \(\{u \in V_n\;|\;\hat{f}(u) \neq 0\;\text{and}\;\hat{h}(u) \neq 0\} = \emptyset\). The authors implement their construction using Gold near-bent functions and general quadratic near-bent functions obtaining bent functions of algebraic degree \(3\), and Kasami-Welch near-bent functions to obtain further not quadratic bent functions. A Boolean function \(f\) of dimension \(n\) is called normal (weakly-normal) if there exists an affine subspace of dimension \(n/2\) on which \(f\) is constant (affine). The authors point out the significance of their construction presenting non-weakly-normal bent functions in dimension \(12\) and \(10\). Until then the smallest dimension where a non-weakly-normal bent function has been found is \(14\), [see \textit{A. Canteaut} et al. Discrete Appl. Math. 154 (2), 202--218 (2006; Zbl 1091.94021)].