Nadia El Mrabet

Duc-Phong Le, Nadia El Mrabet, Safia Haloui et al.

In their seminar paper, Miyaji, Nakabayashi and Takano introduced the first method to construct families of prime-order elliptic curves with small embedding degrees, namely k = 3, 4, and 6. These curves, so-called MNT curves, were then extended by Scott and Barreto, and also Galbraith, McKee and Valenca to near prime-order curves with the same embedding degrees. In this paper, we extend the method of Scott and Barreto to introduce an explicit and simple algorithm that is able to generate all families of MNT curves with any given cofactor. Furthermore, we analyze the number of potential families of these curves that could be obtained for a given embedding degree $k$ and a cofactor h. We then discuss the generalized Pell equations that allow us to construct particular curves. Finally, we provide statistics of the near prime-order MNT curves.

Nadia El Mrabet, Laurent Poinsot

Pairings are particular bilinear maps, and as any bilinear maps they factor through the tensor product as group homomorphisms. Besides, nothing seems to prevent us to construct pairings on other abelian groups than elliptic curves or more general abelian varieties. The point of view adopted in this contribution is based on these two observations. Thus we present an elliptic curve free study of pairings which is essentially based on tensor products of abelian groups (or modules). Tensor products of abelian groups are even explicitly computed under finiteness conditions. We reveal that the existence of pairings depends on the non-degeneracy of some universal bilinear map, called the canonical bilinear map. In particular it is shown that the construction of a pairing on $A\times A$ is always possible whatever a finite abelian group $A$ is. We also propose some new constructions of pairings, one of them being based on the notion of group duality which is related to the concept of non-degeneracy.