Applied Algebra Group at the University of Zürich
Module: MAT076 Arbeitsgemeinschaft in Codierungstheorie und Kryptographie
Event: n.n. Arbeitsgemeinschaft in Codierungstheorie und Kryptographie
Measures of complexity for polynomial system solving over finite field
Prof. Dr. Elisa Gorla's talk
Date: 17.04.19 Time: 16.00 - 17.00 Room: UNINE, B217
Multivariate cryptography is one of a handful of proposal of post-quantum cryptosystems, i.e. cryptosystems that remain secure even in the presence of a quantum computer. In multivariate cryptography, the hard computational problem that one has to solve in order to retrieve the original message from the cyphertext is solving a system of multivariate polynomial equations over a finite field. In this talk, I introduce the current approaches to bounding this complexity. I compare them to each other and discuss some difficulties that arise when one tries to eliminate the heuristics from the complexity estimates. I also present some of my results on specific systems coming from multivariate cryptography.