Elisa Gorla – University of Neuchâtel

Multivariate cryptography and Groebner bases — Colloquium talk

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 equations over a finite field is computationally hard. Groebner bases allow us to solve systems of polynomial equations. Therefore, estimating how long it takes to compute the Groebner basis of a given system of polynomial equations is of fundamental importance for assessing the security of multivariate cryptosystems. In this talk, I will introduce multivariate cryptography and Groebner bases. I will then discuss how results on the complexity of computing Groebner bases affect the security of multivariate cryptosystems and which tools from algebra are relevant in this analysis.