首页|Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
Practical complexities of probabilistic algorithms for solving Boolean polynomial systems
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
? 2021 Elsevier B.V.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δn), for some δ∈(0,1) depending only on the degree of the system, thus beating the brute-force complexity O?(2n). Later, Bj?rklund et al. (2019) and then Dinur (2021) improved this method and devised probabilistic algorithms with a smaller exponent coefficient δ. 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.
NSTL
Elsevier
