**Practical complexities of probabilistic algorithms for solving Boolean polynomial systems**

*Stefano Barbero and Emanuele Bellini and Carlo Sanna and Javier Verbel*

**Abstract: **Solving a polynomial system over a finite field is an NP-complete problem of fundamental importance in both pure and applied mathematics.
In~particular, the security of the so-called multivariate public-key cryptosystems, such as HFE of Patarin and UOV of Kipnis et~al., is based on the postulated hardness of solving quadratic polynomial systems over a finite field.
Lokshtanov et al.~(2017) were the first to introduce a probabilistic algorithm that, in the worst-case, solves a Boolean polynomial system in time $O^{*}(2^{\delta n})$, for some $\delta \in (0, 1)$ depending only on the degree of the system, thus beating the brute-force complexity $O^{*}(2^n)$.
Later, B\"jorklund et al.~(2019) and then Dinur~(2021) improved this method and devised probabilistic algorithms with a smaller exponent coefficient $\delta$.

We survey the theory behind these probabilistic algorithms, and we illustrate the results that we obtained by implementing them in C. In~particular, for random quadratic Boolean systems, we estimate the practical complexities of the algorithms and their probabilities of success as their parameters change.

**Category / Keywords: **implementation / implementation, Boolean quadratic polynomial systems, polynomial method, probabilistic algorithm

**Date: **received 5 Jul 2021, last revised 5 Jul 2021

**Contact author: **eemanuele bellini at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20210708:135729 (All versions of this report)

**Short URL: **ia.cr/2021/913

[ Cryptology ePrint archive ]