Cryptology ePrint Archive: Report 2021/913

Practical complexities of probabilistic algorithms for solving Boolean polynomial systems

Stefano Barbero and Emanuele Bellini and 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.

Category / Keywords: implementation / implementation, Boolean quadratic polynomial systems, polynomial method, probabilistic algorithm

Date: received 5 Jul 2021, last revised 5 Jul 2021

Contact author: eemanuele bellini at gmail com

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2021/913

[ Cryptology ePrint archive ]