Efficient Final Exponentiation for Cyclotomic Families of Pairing-Friendly Elliptic Curves with Any Prime Embedding Degrees

Abstract

Pairings on elliptic curves consisting of the Miller loop and final exponentiation are used for innovative protocols such as ID-based encryption and group signature authentication. As the recent progress of attacks for the discrete logarithm problem in finite fields in which pairings are defined, the importance of the use of curves with prime embedding degrees k has been increased. In this paper, the authors provide formulas to construct algorithms for computing the final exponentiation for cyclotomic families of curves with any prime k. Since the formulas give rise to one of the same exponents given by a lattice-based method for the small cases of k, it is expected that the proposed algorithms are efficient enough for the cases of any prime k. At least for the curves with k = 13 and 19 for the pairing at the 128-bit security level, the proposed algorithms can achieve current state-of-the-art computations.