Probabilistic estimation of the algebraic degree of Boolean functions

The algebraic degree is an important parameter of Boolean functions used in cryptography. When a function in a large number of variables is not given explicitly in algebraic normal form, it is usually not feasible to compute its degree, so we need to estimate it. We propose a probabilistic test for deciding whether the algebraic degree of a Boolean function f is below a certain value k. If the degree is indeed below k, then f will always pass the test, otherwise f will fail each instance of the test with a probability dt_k(f), which is closely related to the average number of monomials of degree k of the polynomials which are affine equivalent to f. The test has a good accuracy only if this probability dt_k(f) of failing the test is not too small. We initiate the study of dt_k(f) by showing that in the particular case when the degree of f is actually equal to k, the probability will be in the interval (0.288788, 0.5], and therefore a small number of runs of the test will be sufficient to give, with very high probability, the correct answer. Exact values of dt_k(f) for all the polynomials in 8 variables were computed using the representatives listed by Hou and by Langevin and Leander.