Section: Overall Objectives

Main topics

TANC is located in the Laboratoire d'Informatique de l'École polytechnique (LIX). The project was created on the 10th of March 2003.

The aim of the TANC project is to promote the study, implementation and use of robust and verifiable asymmetric cryptosystems based on algorithmic number theory.

It is clear from this statement that we combine high-level mathematics with efficient programming. Our main area of competence and interest is that of algebraic curves over finite fields, and most notably their computational aspects; these objects appear as a substitute for modular arithmetic in new analogues of old-fashioned cryptography. One reason for this change is that we can achieve an equivalent security level with a much smaller key size. Our research contributes to the global search for a diverse range of secure substitutes for the famous RSA (Rivest–Shamir–Adleman) cryptosystem, in case some attack appears and destroys the products that use it.

Whenever possible, we produce certificates (proofs) of validity for the objects and systems we build. For instance, an elliptic curve has many invariants, and their values need to be proved, since they may be difficult to (re-)compute.

Our research area includes:

• Fundamental number theoretic algorithms: We are interested in primality proving algorithms based on elliptic curves, integer factorization, and the computation of discrete logarithms over finite fields. These problems lie at the heart of the security of arithmetic based cryptosystems.

• Algebraic curves over finite fields: We tackle algorithmic problems involving efficiently computing group laws on Jacobians of curves, evaluating the cardinality of these objects, and studying the security of the discrete logarithm problem in such groups. These topics are crucial to the applicability of these objects in real crypto products. The theory of curves over finite fields is also essential in the field of AG codes, and the algorithmic aspects of curves and their Jacobians are important for good implementations and analysis.

• Complex multiplication: The theory of Complex Multiplication is a meeting point of algebra, complex analysis and algebraic geometry. Its applications range from primality proving to the efficient construction of elliptic and hyperelliptic curve-based cryptosystems.

• List Decoding of Algebraic codes Using List Decoding one can fight adversarial noise at the same level as the Shannon limit for stochastic noise.

• Decoding algorithms for Algebraic Geometric codes: We use our algorithmic knowledge to accelerate decoding algorithms, be they the classical one (up to half to the minimum distance), or new ones which decode many more errors.