Estimating the nonlinearity of Boolean functions using probabilistic linearity tests

In this paper we concentrate on estimating the nonlinearity of Boolean functions, by probabilistic methods, when it is not feasible to compute the full Walsh transform. Firstly, we improve upon the bounds on the probabilities of failure of existing affinity tests. Secondly, we provide probabilistic tests for estimating nonlinearity based upon either affinity tests or linearity tests (such as the BLR test) and analyze the accuracy of the estimation.