Multivariate Cryptography and Polynomial Systems Complexity by Elisa Gorla (University of Neuchatel)

Title : Multivariate cryptography and the complexity of polynomial systems solving. by Elisa Gorla (University of Neuchatel) Switzerland Abstract The security of multivariate cryptographic primitives relies on the hardness of computing the solutions of multivariate polynomial systems over finite fields. Since we can compute the solutions of a polynomial system from its Groebner basis, bounds on the complexity of Groebner bases computations provide bounds on the security of the corresponding multivariate cryptographic primitives. After introducing multivariate cryptography, Introduce Groebner bases and discuss how to compute them. I will also introduce some invariants, which are used to estimate the complexity of computing a Groebner basis.