Computing the Ate Pairing on Elliptic Curves with Embedding Degree k=9

Xibin LIN  Chang-An ZHAO  Fangguo ZHANG  Yanming WANG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E91-A   No.9   pp.2387-2393
Publication Date: 2008/09/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e91-a.9.2387
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
ate pairing,  cubic twist,  denominator elimination,  final exponentiation,  

Full Text: PDF(214.3KB)>>
Buy this Article

For AES 128 security level there are several natural choices for pairing-friendly elliptic curves. In particular, as we will explain, one might choose curves with k=9 or curves with k=12. The case k=9 has not been studied in the literature, and so it is not clear how efficiently pairings can be computed in that case. In this paper, we present efficient methods for the k=9 case, including generation of elliptic curves with the shorter Miller loop, the denominator elimination and speed up of the final exponentiation. Then we compare the performance of these choices. From the analysis, we conclude that for pairing-based cryptography at the AES 128 security level, the Barreto-Naehrig curves are the most efficient choice, and the performance of the case k=9 is comparable to the Barreto-Naehrig curves.