A fundamental problem in cryptography is to evaluate the security of cryptosystems against the most powerful techniques. To this end, several general methods have been proposed: linear cryptanalysis, differential cryptanalysis, etc. We are interested in applying another general method - algebraic cryptanalysis - to study the security of selected public-key and secret-key cryptosystems. Algebraic cryptanalysis can be described as a general framework that permits to assess the security of a wide range of cryptographic schemes. In fact, the recent development of algebraic cryptanalysis is now widely considered as an important breakthrough in the analysis of cryptographic primitives. It is a powerful technique that applies potentially to a large range of cryptosystems. The basic principle of such cryptanalysis is to model a cryptographic primitive by a system of algebraic equations. The system of equations is constructed in such a way as to have a correspondence between the solutions of this system and secret information of the cryptographic primitive (for instance, the secret key of an encryption scheme).

Multivariate cryptography comprises any cryptographic scheme that uses multivariate polynomial systems. The basic idea of a public-key multivariate scheme is to generate a highly structured set of polynomials which can be easily inverted. Usually, one can consider that this set of polynomials is publicly known. In order to hide the structure, the multivariate polynomials are composed with bijective affine transformations. The resulting set of multivariate polynomials is then the public-key. To encrypt (resp. verify a signature), one simply evaluates the message (resp. signature) on the polynomials of the public-key. To decrypt (resp. sign), one only has to invert the bijective affine transformations and an easy algebraic system. Isomorphism of Polynomials is the basic hard problem that multivariate cryptography relies on. Briefly speaking, this problem consists in recovering transformations between two sets of multivariate polynomial systems. This is equivalent to recovering the secret-key from the public-key.

Algebraic techniques have been successfully applied also in stream cipher cryptanalysis. The feasibility of algebraic cryptanalysis remains the source of speculation for block ciphers. The scientific lock is that the size of the corresponding algebraic systems is so huge (with thousands of variables and equations) that nobody is able to predict correctly the complexity of solving such polynomial systems. The success of algebraic cryptanalysis thus relies on three critical steps: solve efficiently the algebraic systems that model block ciphers; evaluate theoretically and practically the complexity with respect to the system solving tool; use as far as possible the mathematical structure of the underlying mathematical problem to derive an "efficient" algebraic system.

We are interested in developing efficient algorithms for determining the topology of algebraic curves. Most of the previous algorithms for this purpose are CAD-based (i.e., they perform a lifting step after a projection step) and rely on a genericity assumption of geometric nature. The genericity assumption can always be ensured by a generic linear change of variables, which increases the size of the coefficients and then spoils the practical efficiency of the obtained algorithms. More recently, a new algorithm has been proposed by Cheng and others (2009) which allows one to substitute the lifting/projection method by a box-isolating method for the real critical points of the studied curve with respect to a given projection on a coordinate-axis (without any genericity assumption) and counting the number of branches of the curve entering in the box. This algorithm has been designed using general tools (e.g., Gröbner bases and rational univariate representation) for isolating the real solutions of a polynomial system.

To determine the topology of a given algebraic surface and to use triangular meshes to approximately represent the surface are fundamental operations in computer graphics and geometric modeling. Meshing of surfaces could be used to display the surface correctly and to perform engineering applications on the surface, such as the finite element analysis and intersection computation. Significant progresses have occurred in computing the topology of algebraic surfaces by using, e.g., the marching cube method, the Morse theory method, the Delaunay refinement method, and the CAD based method. The central topic of the work focuses on isotopic meshing. Simply speaking, a meshing is isotopic if it has the same topology and the same geometry as the surface. Most of the existing work focuses on algebraic surfaces without singularities. The major challenge now is to develop efficient algorithms to compute ambient isotopic meshing for algebraic surfaces with singularities.

We are interested in producing dynamic diagrams of given geometric objects satisfying given geometric constraint relations. The problem has been studied extensively in the area of computer aided geometric design and modeling, resulting in several approaches such as graph-based, algebraic, numerical, and logic-based approaches. These approaches are mainly for solving geometric constraints that may be expressed algebraically as equalities. The problem of solving geometric constraints involving inequalities, formulated as semi-algebraic systems, has been investigated by Hong and others (2006). The method proposed for computing explicit representations of real solutions of the semi-algebraic systems by radicals proceeds by first decomposing the set of equality constraints into finitely many triangular sets. Then with respect to each triangular set together with inequality constraints, the space of parameters is decomposed into finitely many domains by means of real quantifier elimination, such that associated with each domain there is a set of explicit expressions of the dependent variables in terms of the parameters with radicals. For any given values of the parameters, if they verify the relations of some domain, the values of the dependent variables may be easily computed by direct evaluation of the corresponding explicit expressions.