Integer Variable χ-Based Cross Twisted Ate Pairing and Its Optimization for Barreto-Naehrig Curve

Yasuyuki NOGAMI, Yumi SAKEMI, Hidehiro KATO, Masataka AKANE, Yoshitaka MORIKAWA

Summary :

It is said that the lower bound of the number of iterations of Miller's algorithm for pairing calculation is log ₂r/(k), where () is the Euler's function, r is the group order, and k is the embedding degree. Ate pairing reduced the number of the loops of Miller's algorithm of Tate pairing from ⌊log ₂r⌋ to ⌊ log ₂(t-1)⌋, where t is the Frobenius trace. Recently, it is known to systematically prepare a pairing-friendly elliptic curve whose parameters are given by a polynomial of integer variable "χ." For such a curve, this paper gives integer variable χ-based Ate (Xate) pairing that achieves the lower bound. In the case of the well-known Barreto-Naehrig pairing-friendly curve, it reduces the number of loops to ⌊log ₂χ⌋. Then, this paper optimizes Xate pairing for Barreto-Naehrig curve and shows its efficiency based on some simulation results.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.8 pp.1859-1867
• Publication Date: 2009/08/01
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.E92.A.1859
• Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
• Category: Theory

Authors

Yasuyuki NOGAMI
Yumi SAKEMI
Hidehiro KATO
Masataka AKANE
Yoshitaka MORIKAWA

Keyword

Ate pairing,  Miller's algorithm