SALSA Research team

Solvers for Algebraic Systems and Applications

  • Leader : Jean-Charles Faugere
  • Research center(s) : Paris - Rocquencourt
  • Field : Algorithmics, Programming, Software and Architecture
  • Theme : Algorithms, Certification, and Cryptography
  • Université Pierre et Marie Curie (Paris 6), CNRS, Laboratoire d'informatique de Paris 6 (LIP6) (UMR7606)

Team presentation

Computer Algebra: Polynomial System Solving, Gröbner Bases, Complexity, Real roots, Parametric systems, Algebraic Computational Geometry, Symbolic/Numeric Interaction, Software, High performance Linear Algebra. Cryptology: Algebraic Cryptanalysis, Side Chanel Attacks, Multivariate Public Key Cryptography

Research themes

SALSA is a joint project-team between INRIA, CNRS and University Pierre and Marie Curie. Our group is internationally recognized as one of the leading group in the area of solving systems of polynomial equations/inequalities (non-linear systems) using exact methods. Our goal is to develop efficient algorithms for computing the complex solutions and/or the real ones or in a finite field. SALSA has developed several fundamental algorithms, in particular algorithms for computing Gröbner bases and algorithms based on the so-called critical point method. Complexity issues are also investigated and recently the group has obtained results for structured polynomial systems (systems with symmetries, overdetermined or bilinear systems,…) enabling to identify some classes of problems which can be solved in polynomial time. The practical efficiency of our algorithms relies on highly efficient linear algebra libraries. Hence, the group is involved in the development of parallel high performance linear algebra packages. Algorithms and software developed by SALSA are validated by solving challenging applications arising in scientific computing. Beyond the wide range of studied applications, the group focuses on: • Applications in Cryptology and, in particular, the emerging topic Algebraic Cryptanalysis. The goal is to evaluate the security of a cryptosystem by reducing its study to the solving of an algebraic system with coefficients in a finite field (action CRYPTALG). • Computational Geometry: a new trend in this area is to substitute the manipulation of points and lines with algebraic curves. Intersecting such objects is equivalent to solve an algebraic system (action GEOALG). • Global optimizations problems of algebraic functions leading to new applications in scientific computing (action EXACTA). • Software and algorithms developed by the group have been successfully used in several applications fields: Biology, Robotics and Signal Theory. Our software are devoted to be used in real life applications and teaching. The valorization of this software activity is ensured by their integration in recent releases of the Computer Algebra system Maple (distributed by the WMI Canadian Company) As a prospective subject, we investigate a new research direction which consists in exploiting interactions between symbolic and numeric computing

International and industrial relations

  • WMI (Waterloo Maple Inc.)
  • CELAR and DGA
  • Thalès
  • Joint LIAMA Project ECCA (Reliable Software Theme) INRIA/CNRS/UPMC/CAS
  • ANR grant EXACTA (2010-2013)[programme blanc international]
  • ECRYPT II (2009-2011)- European Network of Excellence for Cryptology
  • Royal Society Project with the Crypto team Royal Holloway, University of London, UK
  • ANR Grant MAC (2007-2010)
  • ANR grant CAC (2009-2012) [programme jeunes chercheurs]
  • Master Parisien de Recherche en Informatique, Master Paris 6

Keywords: Polynomial System solving Real solutions Algebraic Cryptanalysis