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 first 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 affine bilinear system over k[x1,…,xn,y1,…,ym] drops to
polynomial time in n when m is fixed.
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.
