Welcome to the resource topic for 2021/913
Title:
Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
Authors: Stefano Barbero, Emanuele Bellini, Carlo Sanna, 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.
ePrint: https://eprint.iacr.org/2021/913
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .