Efficient GF(3m) Multiplication Algorithm for eta T Pairing

Gen Takahashi; Fumitaka Hoshino; Tetsutaro Kobayashi

Paper 2007/463

Efficient GF(3m) Multiplication Algorithm for eta T Pairing

Gen Takahashi, Fumitaka Hoshino, and Tetsutaro Kobayashi

Abstract

The computation speed of pairing based cryptosystems is slow compared with the other public key cryptosystems even though several efficient computation algorithms have been proposed. Thus more efficient computation of the Tate pairing is an important research goal. GF(3m) multiplication in GF(36m) in the pairing algorithm is the greatest consumer of time. Past research concentrated on reducing the number of GF(3m) multiplications, for instance the Karatsuba method. In this article, we propose a new method to reduce the number of online precomputations( precomputations) in GF(3m) multiplications for the eta T pairing. The proposed algorithm reduces 18 online precomputations in GF(36m) in the eta T pairing to 4 online precomputations by reusing the intermediate products obtained in precomputation.We implement the proposed algorithm and compare the time taken by the proposed algorithm with that of the previous work. Our algorithm offers a 40% performance increase for GF(3m) multiplications in GF(36m) on an AMD 64-bit processor. Additionally, a completely new finding is obtained. The results show that the reducing the number of the multiplications in GF(36m) does not necessarily lead to a speed-up of the eta T pairing calculation.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: elliptic curve cryptosystem
Contact author(s): takahashi gen @ lab ntt co jp
History: 2008-02-07: last of 3 revisions; 2007-12-11: received; See all versions
Short URL: https://ia.cr/2007/463
License: CC BY

BibTeX

@misc{cryptoeprint:2007/463,
      author = {Gen Takahashi and Fumitaka Hoshino and Tetsutaro Kobayashi},
      title = {Efficient {GF}(3m) Multiplication Algorithm for eta T Pairing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2007/463},
      year = {2007},
      url = {https://eprint.iacr.org/2007/463}
}