"Degrees of regularity" - Alessio Caminata

"Degrees of regularity" - Alessio Caminata Seminario del convegno UMI DeCifris del 2021. Abstract: The problem of solving large multivariate polynomial systems over a finite field is ubiquitous in modern public key cryptography. For example, in multivariate cryptography the public key takes the shape of a polynomial system and Gaudry’s index calculus approach to solve the DLP over elliptic curves requires to solve several multivariate polynomial systems. The fastest known algorithms to solve a multivariate polynomial system are the so-called linear algebra based algorithms (F4, F5, XL , MutantXL, . . .). The name comes from the fact that these algorithms transform the problem of solving the system into one or more instances of Gaussian elimination. Linear algebra based algorithms have contributed to breaking many cryptographic challenges. However, correctly estimating the complexity of solving a given system with one of these algorithms is a difficult task. In practice, one would like to be able to estimate the complexity without solving the system, since often this means breaking the corresponding cryptoscheme. For this reason, several authors have introduced and studied different invariants aimed at measuring the complexity of solving a polynomial system with these algorithms. These go by many names such as degree of regular- ity, solving degree, last fall degree, index of regularity, . . . These invariants are strictly connected, however the relations that hold among them are often not so clear and difficult to unravel. In this talk, we will survey some of these invariants and explain the relations among them. Examples will be provided too! The talk is based on a joint work with Elisa Gorla. UMI Crittografia e Codici: https://sites.google.com/view/crittografiaecodici/home?authuser=0 De Cifris: https://www.decifris.it/