Probabilistic estimation of the algebraic degree of Boolean functions

Cryptographic Boolean functions must have high algebraic degree, otherwise they can be approximated as functions of low degree resulting in some attacks being effective such as higher-order differential attacks. However, these functions do not reach the highest possible degree because trade-offs with other parameters need to be considered. When a  Boolean function with a large number of variables is not given explicitly, e.g. it is given as a black box or it is a composition of functions, then it may not be feasible to compute its algebraic degree exactly; so we need to estimate it. From this perspective, we propose a probabilistic test to estimate the algebraic degree with a very high probability.