Welcome to the resource topic for 2012/119
Title:
Accelerating the Final Exponentiation in the Computation of the Tate Pairings
Authors: Taechan Kim, Sungwook Kim, 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.
ePrint: https://eprint.iacr.org/2012/119
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .