Direction de recherche : Antoine JOUX

Co-encadrement : LENSTRA Arjen

Calcul de Groupes de Classes d’un Corps de Nombres et Applications à la Cryptologie

Dans cette thèse, nous nous intéressons au calcul du groupe de classes d'un corps de nombres. Nous débutons par décrire un algorithme de réduction du polynôme de définition d'un corps de nombres. Il existe une infinité de polynômes qui définissent un corps de nombres fixé, avec des coefficients arbitrairement gros. Notre algorithme calcule celui qui a les plus petits coefficients. L'avantage de connaître un petit polynôme de définition est qu'il simplifie les calculs entre éléments de ce corps de nombres, en impliquant des quantités plus petites. En outre, la connaissance d'un tel polynôme permet l'utilisation d'algorithmes plus efficaces que dans le cas général pour calculer le groupe de classes. L'algorithme général pour calculer la structure du groupe de classes repose sur la réduction d'idéaux, vus comme des réseaux. Nous décrivons et simplifions l'algorithme présenté par Biasse et Fieker en 2014 à ANTS et approfondissons l'analyse de complexité. Nous nous sommes aussi intéressés au cas des corps de nombres définis par un polynôme à petits coefficients. Nous décrivons un algorithme similaire au crible par corps de nombres (NFS) dont la complexité en fonction des paramètres du corps de nombres peut atteindre L(1/3). Enfin, nos algorithmes peuvent être adaptés pour résoudre un problème lié : le Problème de l'Idéal Principal. Étant donné n'importe quelle base d'un idéal principal (généré par un seul élément), nous sommes capables de retrouver ce générateur. Cette application de nos algorithmes fournit une attaque efficace contre certains schémas de chiffrement homomorphe basés sur ce problème.

Publications 2016-2017

• 2017
  • A. Gelin : “Calcul de Groupes de Classes d’un Corps de Nombres et Applications à la Cryptologie”, soutenance de thèse, soutenance 22/09/2017, direction de recherche Joux, Antoine, co-encadrement : Lenstra, Arjen (2017)
  • A. Gélin, Th. Kleinjung, Arjen K. Lenstra : “Parametrizations for Families of ECM-Friendly Curves”, Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, Kaiserslautern, Germany, July 25-28, 2017, Kaiserslautern, Germany, pp. 165-171 (2017)
  • J.‑F. Biasse, Th. Espitau, P.‑A. Fouque, A. Gélin, P. Kirchner : “Computing generator in cyclotomic integer rings: A subfield algorithm for the Principal Ideal Problem in Ll∆Kl(1/2) and application to cryptanalysis of a FHE scheme”, Advances in Cryptology – EUROCRYPT 2017 36^th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 – May 4, 2017, Proceedings, Part I, vol. 10210, Lecture Notes in Computer Science, Paris, France, pp. 60-88 (2017)
  • A. Gélin, B. Wesolowski : “Loop-Abort Faults on Supersingular Isogeny Cryptosystems”, Post-Quantum Cryptography - 8^th International Workshop, PQCrypto 2017, Utrecht, The Netherlands, June 26-28, 2017, Proceedings, vol. 10346, Lecture Notes in Computer Science, Utrecht, Netherlands, pp. 93-106 (2017)
• 2016
  • A. Gélin, A. Joux : “Reducing number field defining polynomials: an application to class group computations”, Algorithmic Number Theory Symposium XII, vol. 19 (A), LMS Journal of Computation and Mathematics, Kaiserslautern, Germany, pp. 315-331 (2016)