Sites Inria

Version française

TANC Research team

Algorithmic number theory for cryptology

  • Leader : Daniel Augot
  • Research center(s) : CRI Saclay - Île-de-France
  • Field : Algorithmics, Programming, Software and Architecture
  • Theme : Algorithms, Certification, and Cryptography
  • Partner(s) : Ecole Polytechnique,CNRS
  • Collaborator(s) : EC. POLYTECHNIQUE, CNRS

Team presentation

The goal of the TANC project-team is to promote the study, the programming and the use of robust and verifiable asymmetric cryptosystems based on algorithmic number theory.

Ideas coming from arithmetic have brought robust cryptographic primitives which are now ready to be used in many contexts requiring protected transactions. Beside the problem of confidentiality which is crucial in all types of communication networks, the market is now ready to welcome the electronic signature.

Some problems which have the reputation of being hard have been transformed into enciphering primitives. These are used as building blocks in more complex algorithms resisting different attack scenarios. In turn, these algorithms are integrated in protocols which are then implemented. Our activity lies at the beginning of this chain: we are interested in the problems on which the modern cryptosystems rely, in their often mathematical nature, and in the efficient and robust construction of the corresponding objects.

Project-team TANC is geographically situated at the Laboratoire d'Informatique de l'Ecole polytechnique.

Research themes

  • Algorithmic arithmetic theory We are interested in the elliptic curve based primality proving (F. Morain is the leader in the subject), in the integer factorization, and in the discrete logarithm problem in finite fields. These problems are the keystones of the algorithmic arithmetic theory and of the cryptosystems based upon it.
  • Complex multiplication The theory of complex multiplication is a meeting point of algebra, complex analysis and algebraic geometry. Its applications include primality proving and efficient construction of elliptic cryptosystems based on curves.
  • Algebraic curves over finite fields The algorithmic problems that we consider are the efficient computation of the group law in the jacobians of curves, the computation of the group order and more generally of the ring of endomorphisms, and the discrete log problem in these groups. All of these are crucial points for the construction of robust cryptosystems based on curves.
  • Construction of robust cryptosystems We plan to put together the previous themes in order to efficiently build robust cryptosystems based on RSA or elliptic curves. As far as possible, we try to give proofs or certificates of the important arithmetical properties.

Keywords: Algorithmic number theory Cryptology