Sites Inria

English version

Equipe de recherche SPACES

Rapports d'activité

Overall Objectives

Until the beginning of 2004, the Spaces project-team was a joint project-team of INRIA Lorraine and INRIA Rocquencourt. The main objective of this team was to solve systems of polynomial equations and inequations. The focus was on algebraic methods which are more robust and frequently more efficient than purely numerical tools. The members of the team located in Paris was mostly working on the algebraic aspects, whereas the task of the members located in Nancy was to devise arithmetic tools which could enhance the efficiency of the formal method (mainly real arithmetic, but also more exotic ones, like modular or p-adics).

Since the beginning of 2004, the ``Paris subteam'' has decided to create their own project team. In the same time, due to several arrivals in the project-team, the main interest of the ``Nancy subteam'' has somewhat shifted towards arithmetics, algorithmic number theory and their application in cryptology. A new project-team named CACAO has been created on October 9, 2006. However, from the beginning of 2004, all work done in the Nancy part of the SPACES project should be thought of as being related to the goals of the CACAO project team. We thus choose to present the objectives of the latter project, and results obtained with respect to them. The present activity report is thus a ``joint report'' Spaces-Cacao.

The objectives of the project-team have been along the following lines:

Studying the arithmetic of curves of small genus >1, having in mind applications to cryptology,

Improving the efficiency and the reliability of arithmetics in a very broad sense (i.e., the arithmetics of a wide variety of objects).

These two objectives strongly interplay. On the one hand, arithmetics are, of course, at the core of optimizing algorithms on curves, starting evidently with the arithmetic of curves themselves. On the other hand, curves can sometimes be a tool for some arithmetical problems like integer factorization.

To reach these objectives, we have isolated three key axes of work:

Algebraic Curves: the main issue here is to investigate curves of small genus >1over finite fields (base field , for various pand n), i.e., mainly: to compute in the Jacobian of a given curve, to be able to check that this variety is suitable for cryptography (cardinality, smoothness test) and to solve problems in those structures (discrete logarithm). Applications go from number theory (integer factorization) to cryptography (an alternative to RSA).

Arithmetics: we consider here algorithms working on multiple-precision integers, floating-points numbers, p-adic numbers and finite fields. For such basic data structures, we do not expect new algorithms with better asymptotic behavior to be discovered; however, since those are first-class objects in all our computations, every speedup is most welcome, even by a factor of 2

Linear Algebra and Lattices: Solving large linear systems is a key point of factoring and discrete logarithm algorithms, which we need to investigate if curves are to be applied in cryptology. Lattices are central points of the new ideas that have emerged over the very last years for several problems in computer arithmetic or discrete logarithms algorithms.

Starting Fall 2006, Spaces will lead an ANR research grant on the topic of the Number Field Sieve integer factorization algorithm. This research will be done in collaboration with the teams of LIX (École polytechnique, Palaiseau) and IECN (Nancy). The three research axes set above in the objectives of Spaces fit well in the perspective of this research project.

Another new direction of research has started since Fall 2006 with the arrival of Marion Videau, who has been hired as an assistant professor at UHP, coming from the CODES project-team (Rocquencourt). This should allow the project-team to start an axis around symmetric primitives for cryptology; this is an interesting complement to the expertise already present regarding asymmetric (and especially curve-based) primitives for cryptology.

Suivez Inria