A characterization of binary bent functions (Q2563720)

Bent functions are Boolean functions used in cryptography. They can be defined as those functions that reach the maximum Hamming distance to the set of all affine functions defined on \(V=GF(2)^n\). An alternative definition uses the property of a bent function \(f\) that the Fourier coefficients of \(F:x\mapsto (-1)^{f(x)}\) are \(\pm1\) only (or, equivalently, the Walsh coefficients are \(\pm2^{n\over 2}\) only). In 1995, the first author [IEEE Trans. Inf. Theory 41, 1482-1487 (1995; Zbl 0831.94022)] constructed bent functions by means of characteristic functions \(\chi_{E_i}\) of \({n\over 2}\)-dim subspaces \(E_i\) of \(V\) and suggested the following characterization of bent functions which is now proved to be true. If \(f\) is a Boolean function on \(V=GF(2)^n\), then \(f\) is a bent function iff there exist \({n\over 2}\)-dimensional subspaces \(E_1,\dots,E_k\) of \(V\) and integers \(m_1,\dots,m_k\) such that for all \(x\in V\) \[ f(x)=\sum m_i \chi_{E_i}(x)+2^{{n\over 2}-1} \chi_{\{0\}}(x)\quad \pmod 2^{n\over 2}. \] This characterization is a big step to better understanding of bent functions.