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 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.
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
- 2021-11-27: revised
- 2021-07-08: 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} }