Cryptology ePrint Archive: Report 2008/490

On the final exponentiation for calculating pairings on ordinary elliptic curves

Michael Scott and Naomi Benger and Manuel Charlemagne and Luis J. Dominguez Perez and Ezekiel J. Kachisa

Abstract: When using pairing-friendly ordinary elliptic curves to compute the Tate and related pairings, the computation consists of two main components, the Miller loop and the so-called final exponentiation. As a result of good progress being made to reduce the Miller loop component of the algorithm (particularly with the discovery of ``truncated loop'' pairings like the R-ate pairing), the final exponentiation has become a more significant component of the overall calculation. Here we exploit the structure of pairing friendly elliptic curves to reduce the computation required for the final exponentiation to a minimum.

Category / Keywords: implementation / Tate Pairing

Date: received 20 Nov 2008, last revised 24 Aug 2010

Contact author: mike at computing dcu ie

Available format(s): PDF | BibTeX Citation

Note: Thanks to Yu Chen and Fre Vercauteren for pointing out an error in the sign of x for the BN curves.

Version: 20100824:161833 (All versions of this report)

Short URL: ia.cr/2008/490