Supervision : Annick VALIBOUZE

Calcul efficace de corps de décomposition

Cette these traite des aspects effectifs de la theorie de Galois. Son axe principal est le calcul du corps de décomposition d'un polynome f et de la représentation symétrique de son groupe de Galois. Ici, le corps de décomposition de f est représenté à l'aide d'un idéal des relations de ce polynome. Nous nous attachons à améliorer l'efficacité de ces calculs en prenant en compte le lien entre cet idéal et le groupe de Galois de f. Dans la première partie, nous étudions les idéaux de Galois et les variétés algébriques qui leur correspondent. Nous donnons un algorithme pour le calcul du groupe des permutations laissant stable un idéal triangulaire en n indéterminées. Nous montrons que cet algorithme nécéssite au plus O(n^3) calculs de formes normales dans le cas d'un idéal de Galois pur. En corollaire, nous obtenons un algorithme pour le calcul d'une représentation symétrique du groupe de Galois d'un corps de décomposition qui est de meilleur complexité que ceux connus auparavant.
Dans la deuxième partie, nous étudions le calcul simultané d'un idéal des relations du polynome f et de la représentation symétrique du groupe de Galois correspondant. Nous montrons comment utiliser les informations intermédiaires de la factorisation dans les extensions afin d'améliorer l'efficacité du calcul. Nous appliquons ce principe dans une méthode qui commence par factoriser le polynome sur son corps de rupture et termine en utilisant l'algorithme GaloisIdéal de A. Valibouze. Dans la troisième partie, nous revisitons un algorithme de K. Yokoyama. Cet algorithme prend en entrée l'action du groupe de Galois du polynome f sur des approximations p-adiques de ses racines et retourne un idéal des relations de f. Pour ce faire, il doit résoudre des systèmes linéaires. Nous montrons comment l'optimiser en évitant des calculs et en réduisant la taille des systèmes linéaires qui restent à résoudre.

3 PhD graduated 2012 - 2015

2003-2019 Publications

• 2019
  • A. Bauer, H. Gilbert, G. Renault, M. Rossi : “Assessment of the Key-Reuse Resilience of NewHope”, CT-RSA 2019 - The Cryptographers' Track at the RSA Conference, vol. 11405, Lecture Notes in Computer Science, San Francisco, United States, pp. 272-292, (Springer) (2019)
• 2018
  • L. Barthélémy, D. Kahrobaei, G. Renault, Z. Šunić : “Quadratic time algorithm for inversion of binary permutation polynomials”, ICMS 2018 - International Congress on Mathematical Software, vol. 10931, Lecture Notes in Computer Science, South Bend, IN, United States, pp. 19-27, (Springer) (2018)
• 2016
  • G. Renault : “Contribution à la Résolution Algébrique et Applications en Cryptologie”, habilitation, defence 12/08/2016 (2016)
  • L. Barthélémy, N. Eyrolles, G. Renault, R. Roblin : “Binary Permutation Polynomial Inversion and Application to Obfuscation Techniques”, Proceedings of the 2^nd International Workshop on Software PROtection, Vienna, Austria, (ACM) (2016)
  • J.‑S. Coron, J.‑Ch. Faugère, G. Renault, R. Zeitoun : “Factoring $N=p^r q^s$ for Large $r$ and $s$”, RSA Conference Cryptographers' Track, Topics in Cryptology – CT-RSA 2016, San Francisco, United States (2016)
  • G. Renault, T. Vaccon : “On the p-adic stability of the FGLM algorithm”, (2016)
• 2014
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Sub-cubic Change of Ordering for Gröner Basis: A Probabilistic Approach”, ISSAC '14 - Proceedings of the 39^th International Symposium on Symbolic and Algebraic Computation, Kobe, Japan, pp. 170-177, (ACM) (2014)
  • J.‑Ch. Faugère, L. Huot, A. Joux, G. Renault, V. Vitse : “Symmetrized summation polynomials: using small order torsion points to speed up elliptic curve index calculus”, EUROCRYPT 2014 - 33^rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 8441, Lecture Notes in Computer Science, Copenhagen, Denmark, pp. 40-57, (Springer) (2014)
  • J. Bi, J.‑S. Coron, J.‑Ch. Faugère, Phong Q. Nguyen, G. Renault, R. Zeitoun : “Rounding and Chaining LLL: Finding Faster Small Roots of Univariate Polynomial Congruences”, PKC 2014 - 17^th IACR International Conference on Practice and Theory of Public-Key Cryptography, vol. 8383, Lecture Notes in Computer Science, Buenos Aires, Argentina, pp. 185-202, (Springer) (2014)
• 2013
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Using Symmetries in the Index Calculus for Elliptic Curves Discrete Logarithm”, Journal of Cryptology, pp. 1-40, (Springer Verlag) (2013)
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Polynomial Systems Solving by Fast Linear Algebra”, (2013)
  • G. Barbu, A. Battistelllo, G. Dabosville, Ch. Giraud, G. Renault, S. Renner, R. Zeitoun : “Combined Attack on CRT-RSA. Why Public Verification Must Not Be Public?”, PKC 2013 - Public-Key Cryptography, vol. 7778, Lecture Notes in Computer Science, Nara, Japan, pp. 198-215, (Springer) (2013)
• 2012
  • S. Orange, G. Renault, K. Yokoyama : “Efficient Arithmetic in Successive Algebraic Extension Fields Using Symmetries”, Mathematics in Computer Science, vol. 6 (3), pp. 217-233, (Springer) (2012)
  • C. Carlet, J.‑Ch. Faugère, Ch. Goyet, G. Renault : “Analysis of the algebraic side channel attack”, Journal of Cryptographic Engineering, vol. 2 (1), pp. 45-62, (Springer) (2012)
  • J.‑Ch. Faugère, L. Perret, Ch. Petit, G. Renault : “Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Fields”, Eurocrypt 2012 - 31^st Annual International Conference on the Theory and Applications of Cryptographic Techniques, vol. 7237, Lecture Notes in Computer Science, Cambridge, United Kingdom, pp. 27-44, (Springer) (2012)
  • J.‑Ch. Faugère, Ch. Goyet, G. Renault : “Attacking (EC)DSA Given Only an Implicit Hint”, Selected Areas in Cryptography, vol. 7707, Lecture Notes in Computer Science, Windsor, Canada, pp. 252-274, (Springer) (2012)
  • J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Using Symmetries and Fast Change of Ordering in the Index Calculus for Elliptic Curves Discrete Logarithm”, SCC 2012 - Third international conference on Symbolic Computation and Cryptography, Castro Urdiales, Spain, pp. 113-118 (2012)
• 2011
  • J.‑Ch. Faugère, Ch. Goyet, G. Renault : “Algebraic Side Channel Analysis”, COSADE'11: The 2^nd International Workshop on Constructive Side-Channel Analysis and Secure Design, Darmstadt, Germany, pp. 1-6 (2011)
• 2010
  • J.‑Ch. Faugère, R. Marinier, G. Renault : “Implicit Factoring with Shared Most Significant and Middle Bits”, SCC '10: Proceedings of the 2^nd International Conference on Symbolic Computation and Cryptography, London, United Kingdom, pp. 197-201 (2010)
  • J.‑Ch. Faugère, R. Marinier, G. Renault : “Implicit Factoring with Shared Most Significant and Middle Bits”, in 13^th International Conference on Practice and Theory in Public Key Cryptography -- PKC 2010, vol. 6056, Lecture Notes in Computer Science, Paris, France, pp. 70-87, (Springer-Verlag) (2010)
  • J.‑G. Kammerer, R. Lercier, G. Renault : “Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time”, Pairing-Based Cryptography, vol. 6487, Lecture Notes in Computer Science, Ishikawa, Japan, pp. 278-297, (Springer) (2010)
• 2009
  • S. Orange, G. Renault, K. Yokoyama : “Computation Schemes for Splitting Fields of Polynomials”, ISSAC '09: Proceedings of the 2009 international symposium on Symbolic and algebraic computation, Seoul, Korea, Republic of, pp. 279-286, (ACM) (2009)
  • M. Kida, G. Renault, K. Yokoyama : “QUINTIC POLYNOMIALS OF HASHIMOTO–TSUNOGAI, BRUMER AND KUMMER”, International Journal of Number Theory, vol. 05 (4), pp. 555-571, (World Scientific Publishing) (2009)
• 2008
  • G. Renault : “Introduction à la Théorie de Galois Effective”, chapitre de Journées Nationales du Calcul Formel 2008, pp. 145-195 (2008)
• 2007
  • V. Ménissier‑Morain, Ch. Queinnec, G. Renault : “Environnement de développement -- annales corrigées, avril 2005-janvier 2007”, (Paracamplus, Paris, France), (ISBN: 978-2-916466-04-0) (2007)
• 2006
  • G. Renault, K. Yokoyama : “A Modular Method for Computing the Splitting Field of a Polynomial”, Algorithmic Number Theory Symposium 7^th International Symposium, ANTS-VII, Berlin, Germany, July 23-28, 2006, Proceedings, vol. 4076, Lecture Notes in Computer Science, Berlin, Germany, pp. 124-140, (Springer-Verlag) (2006)
  • G. Renault : “Computation of the Splitting Field of a Dihedral Polynomial”, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, Genova, Italy, pp. 290-297, (ACM Press) (2006)
  • V. Ménissier‑Morain, Ch. Queinnec, G. Renault : “Environnement de développement -- annales corrigées, novembre 2004-janvier 2006”, (Paracamplus, Paris, France), (ISBN: 978-2-916466-02-9) (2006)
• 2005
  • G. Renault : “Calcul efficace de corps de décomposition”, thesis, defence 06/16/2005, supervision Valibouze, Annick (2005)
  • S. Orange, G. Renault, A. Valibouze : “A new tools for computing Galois Groups and Galois Ideals”, (2005)
  • S. Orange, G. Renault, A. Valibouze : “Une note sur les relations entre les racines d’un polynôme réductible”, RAIRO - Theoretical Informatics and Applications (RAIRO: ITA), vol. 39 (4), pp. 651-659, (EDP Sciences) (2005)
• 2004
  • I. Abdeljaouad‑Tej, S. Orange, G. Renault, A. Valibouze : “Computation of the decomposition group of a triangular ideal”, Applicable Algebra in Engineering, Communication and Computing, vol. 15 (3-4), pp. 279-294, (Springer Verlag) (2004)
• 2003
  • S. Orange, G. Renault, A. Valibouze : “Calcul efficace de corps de décomposition”, (2003)
  • S. Orange, G. Renault, A. Valibouze : “Corps de décomposition d’un polynôme réductible”, (2003)