Bounds for the average degree-k monomial density of Boolean functions

Abstract In cryptographic applications, Boolean functions are typically represented in algebraic normal form, i.e. as multivariate polynomial functions over the finite field $${\mathbb {F}}_2$$ . For such a function $$f$$ , we consider, for each degree $$k$$ , the density of monomials of degree $$k$$ in $$f$$ , i.e. the number of monomials of degree $$k$$ that appear in $$f$$ , normalized by the total number of possible monomials of degree $$k$$ . We then average this number over all functions which are affine equivalent to $$f$$ ; we call the resulting quantity, denoted by $${\textbf {add}}_{\varvec{k}}\varvec{(f)}$$ , the average degree- $$k$$ monomial density of $$f$$ . This quantity was defined in previous work, and it was shown that it is closely related to a probabilistic test for deciding whether $$\textbf{deg}\varvec{(f)<k}$$ . In this paper, we give lower and upper bounds for $${\textbf {add}}_{\varvec{k}}\varvec{(f)}$$ for functions of any degree $$d$$ (only the particular case $$d=k$$ having been dealt with in previous work). The lower bound is reached; while in general the upper bound is not reached, we show that, except for some border cases, is not far from the actual maximum. There are several consequences of these bounds. Firstly, it answers negatively the following question: Does there exist a function $$f$$ which has no monomials of a particular degree $$k$$ (with $$k\varvec{<} \textbf{deg}\varvec{(f)}$$ ) and, moreover, it still has no monomials of degree $$k$$ , regardless which affine invertible change of coordinates is applied to $$f?$$ Secondly, the $$\textbf{deg}\varvec{(f)\varvec{<}k}$$ probabilistic test is guaranteed to have high accuracy when the actual degree of $$f$$ is not much higher than $$k$$ . Thirdly, while the average of $${\textbf {add}}_{\varvec{k}}\varvec{(f)}$$ over all $$n$$ -variable functions $$f$$ of a fixed degree $$d>k$$ is equal to 0.5 , the distribution of the values is somewhat surprising; when $$\varvec{n\ge }$$ 20 , $$\varvec{n - k\ge }$$ 9 and $$\varvec{d-k\ge }$$ 6 , low values of add $$_{\varvec{k}}(\varvec{f})$$ exist (reaching approximately $$\frac{{\textbf {1}}}{{\textbf {2}}^{\varvec{d-k}}}$$ ), but there are no values higher than around 0.5005 . We also report experimental results for computing exact values of add $$_{\varvec{k}}\varvec{(f)}$$ for functions in 7 variables and results for running the probabilistic test on functions describing the output of the ciphers Trivium, Grain-128a, and SNOW-V.