Jeudi 23 novembre 2023, 14:00 à 15:00

Salle de séminaire du département informatique

Giulia Gaggero

(Université de Neuchatel, Suisse)

A multivariate cryptograpic instance in practice is a multivariate polynomial system. So the security of a protocol rely on the complexity of solving a multivariate polynomial system. During this talk I will explain the invariant to which this complexity depends on: the solving degree. Unfortunately this invariant is hard to compute. We will talk about another invariant, the degree of regularity, that under certain condition, give us an upper bound on the solving degree. Finally we will talk about random polynomial systems and in particular what "random" means to us. We will give an upper bound on both the degree of regularity and the solving degree of such random systems.