*CTL*

24 May 2011 - 14h00

Solving structured polynomial systems and Applications in Cryptology

by Jean-Charles Faugere from INRIA Paris-Rocquencourt Projet SALSA

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.