Direção de pesquisa : Jean-Charles FAUGÈRE

Co-supervisão£o : VITSE Vanessa

The Point Decomposition Problem in Jacobian varieties

The discrete logarithm problem is a fundamental brick of several protocols for secured communications. Its instanciation over elliptic curves enabled the development of efficient asymmetric primitives in embedded systems. Nowadays, elliptic curve based cryptosystems are widely used: it is crucial to estimate precisely the hardness of such systems. Because of the existence of methods to transfer an elliptic discrete logarithm problem into another algebraic curves, together with recent work on genus 2 curves arithmetic, the study of the attacks on the discrete logarithm problem must not be restricted only to elliptic curves. Following this idea, this thesis deals with Index Caculus algorithms, a family of algebraic attacks, over curves with genus greater than 1. These algorithms run in two phases: our work focuses only on the first, called harvesting or collection phase. This phase has several different algebraic modelling that depend on the target curve. The underlying problem amounts to knowing how to efficiently decompose a point in the Jacobian variety into a sum of other points. In a first step, we will present a sieving approach for the harvesting, when "smooth points" are sought. This approach adapts to all curves with genus greater than 1. Our method is experimentally more efficient than the state-of-the-art.
We will then study a variant of Index Calculus called Decomposition attack, and aimed at curves defined over extension fields. In this situation, the harvesting is done by solving multivariate polynomial systems. We will propose a new way to model such systems, that generalizes the notion of elliptic summation polynomials to every kind of algebraic curves. This new approach will be compared to Nagao's in the case of hyperelliptic curves.
Lastly, we will give theoretical and algorithmical improvements for the solving process of those systems, both for our new approach and Nagao's, when the base field has characteristic 2. Using a general presentation and with Gröbner bases methods, we will give a sharp analysis of the impact of these improvements on the complexity of the solving. This analysis, together with a dedicated implementation, enable us to estimate the total running time for a complete harvesting phase in a decomposition attack over a genus 2 curve satisfying realistic security bounds.

Publicações 2015-2018

• 2018
  • J.‑Ch. Faugère, A. Wallet : “The Point Decomposition Problem over Hyperelliptic Curves: toward efficient computations of Discrete Logarithms in even characteristic”, Designs, Codes and Cryptography, vol. 86, pp. 2279–2314, (Springer Verlag) (2018)
• 2016
  • A. Wallet : “Le problème de décomposition de points dans les variétés Jacobiennes”, tese, defesas 14/12/2016, direção de pesquisa Faugère, Jean-Charles, co-supervisão£o : Vitse, Vanessa (2016)
• 2015
  • V. Vitse, A. Wallet : “Improved Sieving on Algebraic Curves”, Progress in Cryptology -- LATINCRYPT 2015, vol. 9230, Lecture Notes in Computer Science, Guadalajara, Mexico, pp. 295-307 (2015)