Gowers \(U_2\) norm as a measure of nonlinearity for Boolean functions and their generalizations (Q2025362): Difference between revisions

In this paper the authors investigate the \textit{generalized Boolean functions} \(f: \mathrm{GF}(2)^n\to {\mathbb{Z}}/q{\mathbb{Z}}\), where \(q>1\) is an integer. The set of such functions is denoted \(\mathrm{GB}_n^q\). For these functions, the authors define the autocorrelation \(C_f^{(q)}(x)\) and the Walsh-Hadamard transform \(H_f^{(q)}(x)\) (\(x\in \mathrm{GF}(2)^n\)), as usual. A function \(f\in \mathrm{GB}_n^q\) is called \textit{gbent} if \(|H_f^{(q)}(x)|=2^{n/2}\) for all \(x\in \mathrm{GF}(2)^n\). In the case \(q=2\), gbent functions are maximally non-linear, in some sense, and so are resistent against certain cryptographic attacks when used to build a stream cipher. If \(\zeta = e^{2\pi i/q}\) and \(f\in \mathrm{GB}_n^q\) then define \(\chi_f = \zeta^f\). For each integer \(\ell \geq 2\), the authors introduce the \(\ell\)-th order Gowers norm of \(\chi^f\), denoted \(||\chi^f||_{U_\ell}\). The definition is a bit cumbersome, so the reader is referred to the paper for details. However, the basic idea is that this Gowers norm gives a measure of the nonlinearity of \(f\). When \(q=2^k\), the authors compute the 2nd order Gowers norm \(||\chi^f||_{U_2}\) in terms of the autocorrelation of \(f\) and the Walsh-Hadamard transform of of \(f\). When \(f\) is gbent, they give a simple explicit formula for \(||\chi^f||_{U_2}\). Finally, the authors introduce \(\mathbb{Z}\)-bent functions and compute the 2nd order Gowers norm in certain interesting cases (which are relatively technical to explain explicitly). For full details, the reader is referred to the original paper.