2018/19 Lecture Series with Elisa Gorla, University of Neuchâtel
10/01/2018 – video
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.
10/02/2018 – video
Rank-metric codes and q-polymatroids
Rank-metric codes are vector subspaces of the vector space of matrices of given size over a finite field, equipped with the distance function induced by the rank. After an introduction to rank-metric codes, I will introduce q-polymatroids — the q-analogue of polymatroids — and associate a pair of q-polymatroids to each rank-metric codes. I will then discuss how several invariants and structural properties of a code, including generalized weights and duality, are captured by the associated q-polymatroids.
10/03/2018 – video
Universal Groebner bases and Cartwright-Sturmfels ideals
Universal Groebner bases are systems of generators of ideals, which are a Groebner basis with respect to any term order. In this talk, I will introduce a family of ideals named after Cartwright and Sturmfels and defined in terms of properties of their multigraded generic initial ideals. These ideals possess the remarkable property that all their initial ideals are radical. Moreover, the family of Cartwright-Sturmfels ideals is closed under several natural operations, including elimination and taking linear sections. Their natural “dual” family also possesses remarkable properties, including the fact that every (multigraded) minimal system of generators is a universal Groebner basis. A connection to universal Groebner bases for determinantal ideals will be discussed.