Paper 2013/119
Speeding up Ate Pairing Computation in Affine Coordinates
Duc-Phong Le and Chik How Tan
Abstract
At Pairing 2010, Lauter et al's analysis showed that Ate pairing computation in affine coordinates may be much faster than projective coordinates at high security levels. In this paper, we further investigate techniques to speed up Ate pairing computation in affine coordinates. On the one hand, we improve Ate pairing computation over elliptic curves admitting an even twist by describing an $4$-ary Miller algorithm in affine coordinates. This technique allows us to trade one multiplication in the full extension field and one field inversion for several multiplications in a smaller field. On the other hand, we investigate pairing computations over elliptic curves admitting a twist of degree $3$. We propose new fast explicit formulas for Miller function that are comparable to formulas over even twisted curves. We further analyze pairing computation on cubic twisted curves by proposing efficient subfamilies of pairing-friendly elliptic curves with embedding degrees $k = 9$, and $15$. These subfamilies allow us not only to obtain a very simple form of curve, but also lead to an efficient arithmetic and final exponentiation.
Metadata
- Available format(s)
-
PDF
- Publication info
- Published elsewhere. Minor revision. ICISC 2012
- DOI
- 10.1007/978-3-642-37682-5_19
- Keywords
- Ate pairing computationfinal exponentiationaffine coordinatescubic twisted curvespairing-friendly elliptic curves
- Contact author(s)
- tslld @ nus edu sg
- History
- 2015-06-26: revised
- 2013-03-05: received
- See all versions
- Short URL
- https://ia.cr/2013/119
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2013/119,
author = {Duc-Phong Le and Chik How Tan},
title = {Speeding up Ate Pairing Computation in Affine Coordinates},
howpublished = {Cryptology {ePrint} Archive, Paper 2013/119},
year = {2013},
doi = {10.1007/978-3-642-37682-5_19},
url = {https://eprint.iacr.org/2013/119}
}