Presentation 2006-07-20
Efficient Algorithm for Tate Pairing
Masaaki SHIRASE, Tsuyoshi TAKAGI, Eiji OKAMOTO,
PDF Download Page PDF download Page Link
Abstract(in Japanese) (See Japanese page)
Abstract(in English) Duursma-Lee algorithm and its variant (ηT pairing) can efficiently compute Tate pairing over supersingular curves with small characteristic. The algorithms consist of three main steps: (1) computations in a finite field. (2) computations hi the extension field of degree 6, (3) exponentiation calculation in the base field. We have to compute relatively slow cube roots in step (3). This paper proposes some novel algorithms for computing ηT pairing without cube root. The proposed algorithms compute 3^i-th power for each value in the i-th loop in step (3), and thus the cube roots are removed (but we obtain the pairing value powered by 3^k for some k). Moreover we propose some efficient algorithms in which two pairings are computed simultaneously and the part of (2) is improved. The proposed algorithms enable to enhance the speed for verifying a Diffie-Hellman pair. We can achieve 30~40% faster computation comparing with the previously known methods.
Keyword(in Japanese) (See Japanese page)
Keyword(in English) Tate pairing / _<ηT> pairing Diffie-Henman pair
Paper # ISEC2006-12,SITE2006-9
Date of Issue

Conference Information
Committee ISEC
Conference Date 2006/7/13(1days)
Place (in Japanese) (See Japanese page)
Place (in English)
Topics (in Japanese) (See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To Information Security (ISEC)
Language JPN
Title (in Japanese) (See Japanese page)
Sub Title (in Japanese) (See Japanese page)
Title (in English) Efficient Algorithm for Tate Pairing
Sub Title (in English)
Keyword(1) Tate pairing
Keyword(2) _<ηT> pairing Diffie-Henman pair
1st Author's Name Masaaki SHIRASE
1st Author's Affiliation Future University-Hakodate School of Systems Information Science()
2nd Author's Name Tsuyoshi TAKAGI
2nd Author's Affiliation Future University-Hakodate School of Systems Information Science
3rd Author's Name Eiji OKAMOTO
3rd Author's Affiliation Graduate School of Systems and Information Engineering, University of Tsukuba
Date 2006-07-20
Paper # ISEC2006-12,SITE2006-9
Volume (vol) vol.106
Number (no) 175
Page pp.pp.-
#Pages 8
Date of Issue