Efficient Algorithms for Tate Pairing

Tetsutaro KOBAYASHI  Kazumaro AOKI  Hideki IMAI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.1   pp.134-143
Publication Date: 2006/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.1.134
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Elliptic Curve Cryptography
Weil pairing,  Tate pairing,  elliptic curve cryptosystem,  fast computation,  

Full Text: PDF(207.6KB)>>
Buy this Article

This paper presents new algorithms for the Tate pairing on a prime field. Recently, many pairing-based cryptographic schemes have been proposed. However, computing pairings incurs a high computational cost and represents the bottleneck to using pairings in actual protocols. This paper shows that the proposed algorithms reduce the cost of multiplication and inversion on an extension field, and reduce the number of calculations of the extended finite field. This paper also discusses the optimal algorithm to be used for each pairing parameter and shows that the total computational cost is reduced by 50% if k = 6 and 57% if k = 8.