Abstract EN:

Pairings were used in cryptography for the first time to transform the elliptic curve discrete logarithm problem into a discrete logarithm problem in the finite field. Later on, it was shown that pairings could be used to build cryptosystems. In this thesis we propose the use of pairings in the study of isogeny volcanoes and the use of isogenies for efficient implementation of pairings. Isogeny volcanoes are graphs whose vertices are elliptic curves and whose edges are l-isogenies. Algorithms allowing to travel on these graphs were developed by Kohel in his thesis (1996) and later on, by Fouquet and Morain (2001). However, up to now, no method was known, to predict, before taking a step on the volcano, the direction of this step. Given a point P of order l on the elliptic curve, we develop a method to decide whether the subgroup generated by P is the kernel of a horizontal isogeny, a descending or an ascending one. Our method, which consists mainly in the computation of a small number of pairings, is very efficient and gives, in most cases, simple algorithms, allowing to navigate on the volcano. The second part of this thesis focuses on the implementation of pairings on elliptic curves in Edwards form. Using an isogeny of degree 4 from the Edwards curve to an elliptic curve in Weierstrass form, we gave the first efficient implementation of Miller's algorithm on Edwards curves. Our method has performances similar to implementations of the same algorithm on the Weierstrass form of an elliptic curve.