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)
- 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
-
CC BY