Optimal Ate Pairing on Elliptic Curves with Embedding Degree 21

Since the advent of pairing based cryptography, much research has been done on the efficient computations of elliptic curve pairings with even embedding degrees. However, little work has been done on the cases of odd embedding degrees and the existing few are to be improved. Thus, Fouotsa& al. have lead on the computation of optimal ate pairings on elliptic curves of embedding degrees k = 9; 15 and 27 which have twists of order three in [1]. According to our research, work does not exist on the case of embedding degree k = 21. This paper considers the computation of optimal ate pairings on elliptic curves of embedding degree k = 21 which have twists of order three too. Mainly, we provide a detailed arithmetic and cost estimation of operations in the tower field of the corresponding extension fields. Using the lattice-based method, we obtained good results of the final exponentiation and improved the theoretical cost for the Miller step at the 192-bits security level.