Nonlinearity, local and global avalanche characteristics of balanced Boolean functions (Q1598824): Difference between revisions

From the author's presentation: For a Boolean function \(f\) define \(\Delta_f(\alpha) =\Sigma_x\widehat{f}(x)\widehat{f}(x\oplus \alpha)\), \(\widehat{f}(x)=(-1)^{f(x)}\), the absolute indicator \(\Delta_f= \max_{\alpha\neq 0}|\Delta_f(\alpha)|\), and the sum-of-squares indicator \(\sigma_f = \Sigma_\alpha\Delta^2_f(\alpha)\). A class of functions with good local avalanche characteristics, bad global avalanche characteristics is constructed, and it is shown that \(2^{2n}(1+p)\leq \sigma_f\leq 2^{3n-2}\), \(\Delta_f= 2^n\), where \(p\) is the number of linear structures of the first half of a strict avalanche criterion balanced function \(f\). Also, some bounds for the nonlinearity of such functions are derived. In a second result, a class of highly nonlinear balanced functions with good local and global avalanche characteristics is constructed. It is shown that for these functions, \(2^{2n+2}\leq \sigma_f\leq 2^{3n+2+\varepsilon}\) \((\varepsilon = 0\) for \(n\) even and \(\varepsilon = 0\) for \(n\) odd).