Paper 2012/119
Accelerating the Final Exponentiation in the Computation of the Tate Pairings
Taechan Kim, Sungwook Kim, and Jung Hee Cheon
Abstract
Tate pairing computation consists of two parts: Miller step and final exponentiation step. In this paper, we investigate how to accelerate the final exponentiation step. Consider an order $r$ subgroup of an elliptic curve defined over $\Fq$ with embedding degree $k$. The final exponentiation in the Tate pairing is an exponentiation of an element in $\Fqk$ by $(q^k1)/r$. The hardest part of this computation is to raise to the power $\lam:=\varphi_k(q)/r$. Write it as $\lam=\lam_0+\lam_1q+\cdots+\lam_{d1}q^{d1}$ in the $q$ary representation. When using multiexponentiation techniques with precomputation, the final exponentiation cost mostly depends on $\kappa(\lambda)$, the size of the maximum of $\lambda_i$. In many parametrized pairingfriendly curves, the value $\kappa$ is about $\left(1\frac{1}{\rho\varphi(k)}\right)\log q$ where $\rho=\log q/\log r$, while random curves will have $\kappa \approx \log q$. We analyze how this small $\kappa$ is obtained for parametrized elliptic curves, and show that $\left(1\frac{1}{\rho\varphi(k)}\right)\log q$ is almost optimal in the sense that for all known construction methods of parametrized pairingfriendly curves it is the lower bound. This method is useful, but has a limitation that it can only be applied to only parametrized curves and excludes many of elliptic curves. In the second part of our paper, we propose a method to obtain a modified Tate pairing with smaller $\kappa$ for {\em any elliptic curves}. More precisely, our method finds an integer $m$ such that $\kappa(m\lambda)=\left(1\frac{1}{\rho\varphi(k)}\right)\log q$ efficiently using lattice reduction. Using this modified Tate pairing, we can reduce the number of squarings in the final exponentiation by about $\left(1\frac{1}{\rho\varphi(k)}\right)$ times from the usual Tate pairing. We apply our method to several known pairing friendly curves to verify the expected speedup.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Tate pairingbilinear mapsfinal exponentiationoptimal pairingpairingfriendly curveselliptic curvesMiller length
 Contact author(s)
 tckim1458 @ gmail com
 History
 20120304: received
 Short URL
 https://ia.cr/2012/119
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/119, author = {Taechan Kim and Sungwook Kim and Jung Hee Cheon}, title = {Accelerating the Final Exponentiation in the Computation of the Tate Pairings}, howpublished = {Cryptology ePrint Archive, Paper 2012/119}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/119}}, url = {https://eprint.iacr.org/2012/119} }