SALSA   LIP6 Calcul Scientifique UMPC

Jean-Charles Faugère

Research Director/Senior Scientist at INRIA (Paris-Rocquencourt Research Center)

Head of the INRIA/UPMC POLSYS project team (former SALSA team).

Adresse Postale:
UFR Ingénierie 919
Boite courrier 169
4, place Jussieu
F-75252 Paris Cedex 05

Tour 26-00 3eme etage

Bureau 317
LIP6 – Université Paris 6
4, place Jussieu
75005 Paris – France
Tél : +33 1 44 27 70 28
Email: Jean-Charles.Faugere [at]



Research Interests:
Polynomial System Solving, Software, Academic and industrial applications, Cryptology, Algebraic Cryptanalysis, Complexity analysis.
Gröbner Bases - Fast implementation - Computer algebra - Certified results - Efficient software, Algebraic Cryptanalysis.

Polynomial System Solving and Gbner Bases ?

The notion of vector space is the dedicated mathematical object when solving linear systems. Similarly the fundamental mathematical object associated to a polynomial system of multivariate equations is the ideal generated by the equations. From an algorithmic point of view the main tool to represent an ideal is a Gröbner basis (Bruno Buchberger). A Gröbner basis is a finite set of polynomials which has desirable algorithmic properties. The historical algorithm to compute Gröbner bases is the Buchberger algoritm; more efficient algorithms (FGLM, F4, F5, fast FGLM) have been proposed to compute Gröbner bases more efficiently. A new trend in the field is to propose dedicated tool to solve structured polynomial systems (for using the symmetries induced by a finite group or the bilinear structure or determinantal ideals). Dedicated methods for finite fields have also been proposed. In practice, FGb is a fast library for computing Grobner Bases that can be used from Maple or from any C program.


Gröbner bases and Cryptography Last years a new kind of cryptanalysis has made its entrance in cryptography: the so-called algebraic cryptanalysis.  In a nutshell, the idea of algebraic cryptanalysis is that for a given cryptosystem one has to generate a suitable algebraic system of equations whose zeroes correspond to the deciphered message or the secret key. A fundamental issue of this cryptanalysis consists thus in finding zeroes of algebraic systems. Gröbner bases, which are a fundamental tool of commutative algebra, constitute the most elegant and efficient way for solving this problem.  They provide an algorithmic solution for solving several problems related to algebraic systems. From a practical point of view, we employed a fast Gröbner basis algorithm, namely F5, for solving the corresponding algebraic system. Very often this approach is efficient in practice and obliges to modify the parameter of the cryptosystem. Some research papers FJ03, AFIK04, AF05, FP06a, FP06b, FLP08, FOPT10, FS10, FMR10, BFFP11, BFP11, AFFP11, FPPR12, BFP12.


HFE vs Random Algebraic System

Complexity of semi-regular systems.


Design of microwave filters

Understanding the complexity of computing Gröbner bases is a fundamental issue. Following step by step the F5 algorithm it is possible to predict quite accurately the complexity of the computation. To this end, it is necessary to understand the shape of the matrices generated by F5 (generic quadratic system of 12 equations in 12 variables) [BFS2014]:

Current Activities
ANR-NFSC EXACTA start in March 2010 - 2013
ANR ANR CAC start in September 2009 - 2012
New ! ANR HPAC will start in january 2012
New ! ANR GEOLMI will start in december 2011

ACA 2014: Special Session: Grobner Bases and Applications Bernd Sturmfels


SCC 2008 - Special Issue March 2010: MCS Special Issue: Symbolic Computation and Cryptography (Download Forword + TOC). Vol 3 No.2 pp 127-224.
Fleche Sept 2011: Invited talk ECC 2011
Fleche Oct 2011: Invited talk SIAM AG11
Fleche June 2011: STOC 2011 best poster award
Fleche July 2010: ISSAC 2010 best student paper award
Event September 13-17 2009 - Invited Talk Kobe CASC 2009 (Japan)


Matrix generated by the F4 algorithm

Recent Activities

* March 2007 Invited talk Fast Software Encryption (FSE 2007, Luxembourg).

* 30 April - 4 May 2007 Emerging Topics in Cryptographic Design and Cryptanalysis, Samos, Greece.

* 11-13 June 2007 Indo-French Workshop in Cryptography.

*  May 2006 Feb 2006 Special Semester on Gröbner Bases “ECC, Crypto”, Linz Autriche

*  Feb 2006 Special Semester on Gröbner Bases

« Efficient Computations », Linz Autriche

* June 2007 3 Talks invited by the CNR (Roma)

*  Nov 2006 FGb and RS at IMA Annual Program,

Minneapolis USA

Some Articles

* F4 algorithm

* F5 algorithm

*  Ridges : ombilics, purple and critical points

*  LLL and Gröbner Bases

*  HFE Challenge broken

CC11 broken

*  Polynomial Equations with symmetries

*  Gröbner Bases and Signal Theory

Last Update: August 14, 2015