Equipe : PolSys

Data de partida : 31/08/2014

http://www-polsys.lip6.fr/~huot/

On the one hand, we present new tools for solving polynomial systems by using Gröbner bases. First, we investigate polynomial systems with symmetries. We show that solving such a system is closely related to solving quasi-homogeneous systems. We thus propose new complexity bounds for solving systems with symmetries. Then, we study the bottleneck of polynomial systems solving: the change of ordering for Gröbner bases. The usual complexity of such algorithms is cubic in the number of solutions and dominates the overall complexity of polynomial systems solving. We propose for the first time change of ordering algorithms with sub-cubic complexity in the number of solutions.

On the other hand, we investigate the index calculus attack of Gaudry to solve the elliptic curve discrete logarithm problem. We highlight some families of elliptic curves that admit particular symmetries. These symmetries imply an exponential gain in the complexity of solving the ECDLP. As a consequence, we obtain new security parameters for some instances of the ECDLP. One of the main steps of this attack requires to compute Semaev summation polynomials. The symmetries of binary elliptic curves allow us to propose a new algorithm based on evaluation-interpolation to compute their summation polynomials. Equipped with this algorithm we establish a new record for the computation of these polynomials.

M. Reynald Lercier (Chercheur associé IRMAR, Ingénieur DGA MI) [Rapporteur]

M. Éric Schost (Associate Professor University of Western Ontario) [Rapporteur]

M. Jean-Charles Faugère (DR INRIA Paris-Rocquencourt)

M. Pierrick Gaudry (DR CNRS)

M. Antoine Joux (Titulaire de la Chaire de Cryptologie de la fondation partenariale de l'UPMC)

M. Guénaël Renault (Maître de Conférences UPMC)

M. Mohab Safey El Din (Professeur UPMC)

M. Benjamin Smith (CR INRIA Saclay-Île-de-France)

- 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 - 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.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Sub-cubic Change of Ordering for Gröner Basis: A Probabilistic Approach”, ISSAC '14 - 39
- 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 (2013)
- L. Huot : “Polynomial systems solving and elliptic curve cryptography”, tese, defesas 13/12/2013, direção de pesquisa Faugère, Jean-Charles, co-supervisão£o RENAULT Guénaël, GAUDRY Pierrick (2013)
- J.‑Ch. Faugère, P. Gaudry, L. Huot, G. Renault : “Polynomial Systems Solving by Fast Linear Algebra”, (2013)

- 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)