Seminar on Applied Geometry and Algebra (SIAM SAGA) featuring Elisa Gorla

For more information, see our website: http://wiki.siam.org/siag-ag/index.php/Webinar



Date: Tuesday, September 14 at 11:00am Eastern time zone


Speaker: Elisa Gorla, University of Neuchâtel


Title: Multivariate cryptography and the complexity of polynomial system solving


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, I will discuss linear-algebra-based methods for computing Groebner bases, which are currently considered the most efficient algorithms available. I will introduce some invariants which control this complexity and try to answer the question of how hard it is to solve a "random" polynomial system.


Moderator: Jose Israel Rodriguez, University of Wisconsin Madison