Nonlinearity of Boolean Functions: An Algorithmic Approach Based on Multivariate Polynomials

Abstract

We review and compare three algebraic methods to compute the nonlinearity of Boolean functions. Two of them are based on Gröbner basis techniques: the first one is defined over the binary field, while the second one over the rationals. The third method improves the second one by avoiding the Gröbner basis computation. We also estimate the complexity of the algorithms, and, in particular, we show that the third method reaches an asymptotic worst-case complexity of $O\left(n{2}^n\right)$ operations over the integers, that is, sums and doublings. This way, with a different approach, the same asymptotic complexity of established algorithms, such as those based on the fast Walsh transform, is reached.