رئاسـة البـحث : Antoine JOUX

تأطـير مـشـترك : 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.

إصدارات 2016-2017

• 2017
  • A. Gelin : “Calcul de Groupes de Classes d’un Corps de Nombres et Applications à la Cryptologie”, أطروحة, مناقـشـة مـذكـرة 22/09/2017, رئاسـة البـحث Joux, Antoine, تأطـير مـشـترك : 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)