Cryptology ePrint Archive: Report 2016/1187

Computing Optimal Ate Pairings on Elliptic Curves with Embedding Degree $9,15$ and $27$

Emmanuel Fouotsa and Nadia El Mrabet and Aminatou Pecha

Abstract: Much attention has been given to efficient computation of pairings on elliptic curves with even embedding degree since the advent of pairing-based cryptography. The existing few works in the case of odd embedding degrees require some improvements. This paper considers the computation of optimal ate pairings on elliptic curves of embedding degrees $k=9, 15 \mbox{ and } 27$ which have twists of order three. Mainly, we provide a detailed arithmetic and cost estimation of operations in the tower extensions field of the corresponding extension fields. A good selection of parameters %at the $128$, $192$ and $256$-bits security level enables us to improve the theoretical cost for the Miller step and the final exponentiation using the lattice-based method comparatively to the previous few works that exist in these cases. In particular for $k=15$ we obtain an improvement, in terms of operations in the base field, of up to $25\%$ in the computation of the final exponentiation. Also, we obtained that elliptic curves with embedding degree $k=15$ present faster results than BN$12$ and KSS$16$ curves at the $128$-bits security levels. At the $192$-bits security level, curves with $k=15$ surprisingly still present faster results compared to KSS$18$ and BLS$24$ curves. We provided a Magma implementation in each case to ensure the correctness of the formulas used in this work.

Category / Keywords: Elliptic Curves \and Optimal Pairings \and Miller's algorithm \and Extension fields arithmetic \and Final exponentiation

Date: received 29 Dec 2016, last revised 4 Oct 2018

Contact author: emmanuelfouotsa at yahoo fr

Available format(s): PDF | BibTeX Citation

Note: We revised this work and added a new section.

Version: 20181004:125302 (All versions of this report)

Short URL: ia.cr/2016/1187


[ Cryptology ePrint archive ]