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^k-1)/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_{d-1}q^{d-1}$ in the $q$-ary representation. When using multi-exponentiation techniques with precomputation, the final exponentiation cost mostly depends on $\kappa(\lambda)$, the size of the maximum of $|\lambda_i|$. In many parametrized pairing-friendly 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 pairing-friendly 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)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
Tate pairingbilinear mapsfinal exponentiationoptimal pairingpairing-friendly curveselliptic curvesMiller length
Contact author(s)
tckim1458 @ gmail com
History
2012-03-04: received
Short URL
https://ia.cr/2012/119
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.