CCIS Seminar - Tuesday 24 May 2011 - CTL
14:00:00 - Salle de CTL

Jean-Charles Faugere, INRIA Paris-Rocquencourt Projet SALSA

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 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.

Home page CCIS Seminars
How to come to CTL -