Category: Seminars and Conferences
State: Archived
18 January 2022 - at 2,30 pm ONLINE

"Practical complexities of probabilistic algorithms for solving boolean polynomial systems" - Javier Verbel

On Zoom platform

Seminar of De Cifris Augustae Taurinorum, in collaboration with the Department of Mathematical Sciences "G.L. Lagrange" of Politecnico di Torino, the Department of Mathematics "G. Peano" of the University of Turin, Quadrans Foundation and Telsy SPA.

"Practical complexities of probabilistic algorithms for solving Boolean polynomial systems"
Javier Verbel - Technology Innovation Institute
Tuesday 18 January 2022, at 2,30 pm

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), 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 δ. 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.

You will be able to follow the seminar through Zoom, at the following link.