CARAMEL Research team
Cryptology, Arithmetic: Hardware and Software
- Leader : Pierrick Gaudry
- Research center(s) : CRI Nancy - Grand Est
- Field : Algorithmics, Programming, Software and Architecture
- Theme : Algorithmics, Computer Algebra and Cryptology
- Partner(s) : CNRS,Université de Lorraine
- Collaborator(s) : CNRS, INRIA
Team presentationA general keyword that could encompass most of our research objectives is arithmetic. Indeed, in the CARAMEL proposal, the goal is to push forward the possibilities to compute efficiently with objects having an arithmetic nature. This includes integers, real and complex numbers, polynomials, finite fields, and, last but not least, algebraic curves.
Our main application domains are public-key cryptography and computer algebra systems. Concerning cryptography, we concentrate on the study of the primitives based on the factorization problem or on the discrete-logarithm problem in finite fields or (Jacobians of) algebraic curves. Both the constructive and destructive sides are of interest to this proposal. For applications in computer algebra systems, we are mostly interested in arithmetic building blocks for integers, floating-point numbers, polynomials, and finite fields. Also some higher level functionalities like factoring and discrete-logarithm computation are usually desired in computer algebra systems.
Since we develop our expertise at various levels, from most low-level software or hardware implementation of basic building blocks to complicated high-level algorithms like integer factorization or point counting, we have remarked that it is often too simple-minded to separate them: we believe that the interactions between low-level and high-level algorithms are of utmost importance for arithmetic applications, yielding important improvements that would not be possible with a vision restricted to low- or high-level algorithms.
Research themesWe emphasize three main directions for our project:
- Integer factorization and discrete-logarithm computation in finite fields
We are in particular interested in the number field sieve algorithm (NFS) that is the best known algorithm for factoring large RSA-like integers, and for solving discrete logarithms in prime finite fields. A sibling algorithm, the function field sieve (FFS) is the best known algorithm for computing discrete logarithms in finite fields of small characteristic. In all these cases, we plan to improve on existing algorithms, with a view towards practical considerations and setting new records.
- Algebraic curves and cryptography
Our two main research interests on this topic lie in genus 2 cryptography and in the arithmetic of pairings, mostly on the constructive side in both cases. For genus 2 curves, a key algorithmic tool that we plan to develop is the computation of explicit isogenies; this will allow improvements for cryptography-related computations such as point counting in large characteristic, complex-multiplication construction and computation of the ring of endomorphisms. For pairings, our principal concern is the optimization of pairing computations, in particular in hardware, or in constrained environments. We will develop automatic tools to help in choosing the most suitable (hyper-)elliptic curve and generating efficient hardware for a given security level and set of constraints.
Integer, finite-field and polynomial arithmetics are ubiquitous to our research. We consider them not only as tools for other algorithms, but as a research theme per se. We are interested in algorithmic advances, in particular for large input sizes where asymptotically fast algorithms become of practical interest. We also keep an important implementation activity, both in hardware and in software.
International and industrial relations
- Long term collaboration with Richard Brent (Canberra, Australia) about efficient arithmetic.
- Long term collaboration with Eric Schost (London, Ontario, Canada) on the topic of genus 2 point counting
- Collaboration with Arjen Lenstra and Thorsten Kleinjung (Lausanne, Switzerland) on integer factorisation
- Co-supervision of a PhD student with Tanja Lange (Eindhoven, Netherlands)
- Collaboration with Francisco Rodríguez-Henríquez (Mexico) on pairing computations