Paper 2021/913
Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
Stefano Barbero, Emanuele Bellini, Carlo Sanna, and Javier Verbel
Abstract
Solving a polynomial system over a finite field is an NPcomplete problem of fundamental importance in both pure and applied mathematics. In~particular, the security of the socalled multivariate publickey 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 worstcase, 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 bruteforce 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.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Published elsewhere. Minor revision. Discrete Applied Mathematics
 DOI
 10.1016/j.dam.2021.11.014
 Keywords
 implementationBoolean quadratic polynomial systemspolynomial methodprobabilistic algorithm
 Contact author(s)
 eemanuele bellini @ gmail com
 History
 20211127: revised
 20210708: received
 See all versions
 Short URL
 https://ia.cr/2021/913
 License

CC BY
BibTeX
@misc{cryptoeprint:2021/913, 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}, url = {https://eprint.iacr.org/2021/913} }