**CCIS Seminar - Tuesday 24 May 2011 - CTL**

*14:00:00 - *__Salle de CTL__## Solving structured polynomial systems and Applications in Cryptology

**Résumé :** *Solving multihomogeneous systems, as a wide range of structured algebraic
systems occurring frequently in practical problems, is of ﬁrst importance.
In this talk, we focus on the particular but important case of bilinear
systems. Recent results enable us explain theoretically why solving these
systems with Gröbner bases algorithms is easier than solving systems of the
same degree. We can take advantage of the multihomogeneous structure of
those systems to propose dedicated algorithms to speed up the Gröbner basis
computations: using a variant of the Bernstein, Sturmfels and Zelevinsky
theorem we can extend the classical F5 criterion to avoid reductions to
zero. Surprisingly, the complexity of computing a Gröbner basis of a generic
0-dimensional aﬃne bilinear system over k[x1,…,xn,y1,…,ym] drops to
polynomial time in n when m is ﬁxed.
In a second part of the talk we discuss some applications of these results
to:
· the MinRank problem (a generalization of the eigenvalue problem to
several matrices) which is at the heart of the security of many multivariate
public key cryptosystems.
· the McEliece cryptosystem which is one of the oldest public key
cryptosystem; its security is based on the hardness of decoding general
linear codes.*

Home page CCIS Seminars

How to come to **CTL** - http://www-verimag.imag.fr/~async/reachus.php