University of Neufchatel (Switzerland)

Multivariate cryptography is one of a handful of proposals for post-quantum cryptographic schemes, i.e. cryptographic schemes that are secure also against attacks carried on with a quantum computer. Their security relies on the assumption that solving a system of multivariate (quadratic) equations over a finite field is computationally hard. 

Groebner bases allow us to solve systems of polynomial equations. Therefore, one of the key questions in assessing the robustness of multivariate cryptosystems is estimating how long it takes to compute the Groebner basis of a given system of polynomial equations. 

After introducing multivariate cryptography and Groebner bases, I will present a rigorous method to estimate the complexity of computing a Groebner basis. This approach is based on techniques from commutative algebra and is joint work with Alessio Caminata (University of Barcelona).