SEMINARIO: "PRACTICAL COMPLEXITIES OF PROBABILISTIC ALGORITHMS FOR SOLVING BOOLEAN POLYNOMIAL SYSTEMS" - JAVIER VERBEL

Webinar su piattaforma Zoom

Seminario di De Cifris Augustae Taurinorum, in collaborazione con il Dipartimento di Scienze Matematiche "G.L. Lagrange" del Politecnico di Torino, il Dipartimento di Matematica "G. Peano" dell'Università degli Studi di Torino, Quadrans Foundation e Telsy SPA.

"Practical complexities of probabilistic algorithms for solving Boolean polynomial systems"
Javier Verbel - Technology Innovation Institute
Martedì 18 gennaio 2022 - ore 14:30

Webinar su piattaforma Zoom visibile all'indirizzo: http://tiny.cc/crypto_webinar.

Abstract: Solving a polynomial system over a finite field is an NP-complete problem of fundamental importance in cryptography. In particular, the security of the so-called multivariate cryptosystems relies in the hardness of this problem. Recently, Lokshtanov et al. (2017) introduced 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^∗(2ⁿ). Later, Björklund et al. (2019) and then Dinur (2021) improved this method and devised probabilistic algorithms with a smaller exponent coefficient δ. In this talk, we are doing to explain the main ideas behind these algorithms and their asymptotically complexities. Also, we illustrate the complexity results that we obtained in practice by implementing them in C.