Paper 2022/1412
Boolean Polynomial Evaluation for the Masses
Abstract
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'10 and of the space-efficient Moebius transform given by Dinur at EUROCRYPT'21. 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'' library called BeanPolE, which we hope could be helpful to other cryptographers. This paper actually contains all the code, which is quite short.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Boolean polynomials exhaustive search software implementation Moebius transform
- Contact author(s)
- charles bouillaguet @ lip6 fr
- History
- 2022-10-23: revised
- 2022-10-18: received
- See all versions
- Short URL
- https://ia.cr/2022/1412
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/1412, author = {Charles Bouillaguet}, title = {Boolean Polynomial Evaluation for the Masses}, howpublished = {Cryptology ePrint Archive, Paper 2022/1412}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1412}}, url = {https://eprint.iacr.org/2022/1412} }