Paper 2022/1412

Boolean Polynomial Evaluation for the Masses

Charles Bouillaguet, Sorbonne Université, Paris, France, LIP6 laboratory, Paris, France
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)
PDF
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
No rights reserved
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.