You are looking at a specific version 20181004:125302 of this paper. See the latest version.

Paper 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.

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

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Contact author(s)
emmanuelfouotsa @ yahoo fr
History
2018-11-15: last of 2 revisions
2017-01-01: received
See all versions
Short URL
https://ia.cr/2016/1187
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.