GELIN Alexandre

PhD student at Sorbonne University
Team : ALMASTY
https://perso.lip6.fr/Alexandre.Gelin

Supervision : Antoine JOUX

Co-supervision : LENSTRA Arjen

Class Group Computations in Number Fields and Applications to Cryptology

In this thesis, we focus on class group computations in number fields. We start by describing an algorithm for reducing the size of a defining polynomial of a number field. There exist infinitely many polynomials that define a specific number field, with arbitrarily large coefficients, but our algorithm constructs the one that has the absolutely smallest coefficients. The advantage of knowing such a ``small'' defining polynomial is that it makes calculations in the number field easier because smaller values are involved. In addition, thanks to such a small polynomial, one can use specific algorithms that are more efficient than the general ones for class group computations. The generic algorithm to determine the structure of a class group is based on ideal reduction, where ideals are viewed as lattices. We describe and simplify the algorithm presented by Biasse and Fieker in 2014 at ANTS and provide a more thorough complexity analysis for~it. We also examine carefully the case of number fields defined by a polynomial with small coefficients. We describe an algorithm similar to the Number Field Sieve, which, depending on the field parameters, may reach the hope for complexity L(1/3). Finally, our results can be adapted to solve an associated problem: the Principal Ideal Problem. Given any basis of a principal ideal (generated by a unique element), we are able to find such a generator. As this problem, known to be hard, is the key-point in several homomorphic cryptosystems, the slight modifications of our algorithms provide efficient attacks against these cryptographic schemes.

Defence : 09/22/2017

Jury members :

M. Andreas ENGE - Directeur de Recherche, Inria Bordeaux-Sud-Ouest & IMB [Rapporteur]
M. Claus FIEKER - Professeur, Université de Kaiserslautern [Rapporteur]
M. Karim BELABAS - Professeur, Université de Bordeaux
M. Louis GOUBIN - Professeur, Université de Versailles-St-Quentin-en-Yvelines
M. Antoine JOUX - Chaire de Cryptologie à la Fondation UPMC, Paris
M. Arjen LENSTRA - Professeur, École Polytechnique Fédérale de Lausanne
Mme Ariane MÉZARD - Professeur, Université Pierre et Marie Curie, Paris
M. Nigel SMART - Professeur, Université de Bristol

Departure date : 09/26/2017

2016-2017 Publications