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 dtk(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 dtk(f) of failing the test is not too small. We initiate the study of dtk(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 dtk(f) for all the polynomials in 8 variables were computed using the representatives listed by Hou and by Langevin and Leander.