Paper 2021/913

Practical complexities of probabilistic algorithms for solving Boolean polynomial systems

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


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.

Available format(s)
Publication info
Published elsewhere. Minor revision. Discrete Applied Mathematics
implementationBoolean quadratic polynomial systemspolynomial methodprobabilistic algorithm
Contact author(s)
eemanuele bellini @ gmail com
2021-11-27: revised
2021-07-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Stefano Barbero and Emanuele Bellini and Carlo Sanna and Javier Verbel},
      title = {Practical complexities of probabilistic algorithms for solving Boolean polynomial systems},
      howpublished = {Cryptology ePrint Archive, Paper 2021/913},
      year = {2021},
      doi = {10.1016/j.dam.2021.11.014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.