Boolean Polynomial Evaluation for the Masses

This article gives improved algorithms to evaluate a multivariate Boolean polynomial over all the possible values of its input variables. Such a procedure is often used in cryptographic attacks against symmetric schemes. More precisely, we provide improved and simplified versions of the Fast Exhaustive Search algorithm presented at CHES\u2710 and of the space-efficient Moebius transform given by Dinur at EUROCRYPT\u2721. The new algorithms require $\mathcal{O}(d 2^n)$ operations with a degree-$d$ polynomial and operate in-place. We provide the full C code of a complete implementation under the form of a ``user-friendly\u27\u27 library called BeanPolE, which we hope could be helpful to other cryptographers. This paper actually contains all the code, which is quite short