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 $\text{Fq}$ with embedding degree $k$. The final exponentiation in the Tate pairing is an exponentiation of an element in $\text{Fqk}$ by $(q^k-1)/r$. The hardest part of this computation is to raise to the power $\text{lam}:={\phi }_k(q)/r$. Write it as $\text{lam}={\text{lam}}_0+{\text{lam}}_{1}q+\cdots +{\text{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 $$ is about $$ where $$, while random curves will have $$. We analyze how this small $$ is obtained for parametrized elliptic curves, and show that $$ 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 $$ for {\em any elliptic curves}. More precisely, our method finds an integer $$ such that $$ efficiently using lattice reduction. Using this modified Tate pairing, we can reduce the number of squarings in the final exponentiation by about $$ times from the usual Tate pairing. We apply our method to several known pairing friendly curves to verify the expected speedup.