Some properties of bent functions (Q2468785)

Let \(V_n=GF(2)^n\) be a linear space of dimension \(n\) over \(GF(2)\). Functions \(f(x)\) from \(V_n\) to \(GF(2)\) are called Boolean functions. They can be represented as polynomials in \(x=(x_1,\dots, x_n)\) over \(GF(2)\) whose degree in each variable \(x_i\), \(i=1,\dots,n\), is at most one. If \(f(x)\) is such a Boolean function, the real-valued function \[ \widetilde f(z)=\sum_{s\in V_n}(-1)^{f(s)+s \cdot z},\;z\in V_n, \] is called the Walsh transform of \(f(x)\), where \(s\cdot z\) stands for the usual scalar product. \(f(x)\) is called a bent function if \(n\) is even and \(|\widetilde f(z)|=2^{n/2}\) for all \(z\in V_n\). Equivalently, \(f(x)\) turns out to be a bent function if and only if for all \(0\neq a\in V_n\), \(f(x)+ f(x+a)\) is a function that takes the values 0 and 1 equally often (this property indicates the significance of bent functions in cryptography). Let \(f(x,y)\) be a Boolean function on \(V_n\) where \(x\in V_{n-1}\) and \(y\in V_1\), then it can be expressed as \(f(x,y)=(y+1)p(x)+yq(x)\), with Boolean functions \(p(x)\), \(q(x)\) on \(V_{n-1}\). The present paper shows several properties of bent functions. In particular, it investigates properties of \(p(x)\) and \(q(x)\) that are necessary and/or sufficient for \(f(x,y)\) to be a bent function. Finally, a lower bound on the number of bent functions on \(V_n\) is given.