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

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

doi:10.1587/transfun.E92.A.1859

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

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

Full Text Views

0

Cite this

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

Publicized

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

Cite this

Copy

Yasuyuki NOGAMI, Yumi SAKEMI, Hidehiro KATO, Masataka AKANE, Yoshitaka MORIKAWA, "Integer Variable χ-Based Cross Twisted Ate Pairing and Its Optimization for Barreto-Naehrig Curve" in IEICE TRANSACTIONS on Fundamentals, vol. E92-A, no. 8, pp. 1859-1867, August 2009, doi: 10.1587/transfun.E92.A.1859.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.1859/_p

Copy

@ARTICLE{e92-a_8_1859,
author={Yasuyuki NOGAMI, Yumi SAKEMI, Hidehiro KATO, Masataka AKANE, Yoshitaka MORIKAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Integer Variable χ-Based Cross Twisted Ate Pairing and Its Optimization for Barreto-Naehrig Curve},
year={2009},
volume={E92-A},
number={8},
pages={1859-1867},
abstract={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.},
keywords={},
doi={10.1587/transfun.E92.A.1859},
ISSN={1745-1337},
month={August},}

Copy

TY - JOUR
TI - Integer Variable χ-Based Cross Twisted Ate Pairing and Its Optimization for Barreto-Naehrig Curve
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1859
EP - 1867
AU - Yasuyuki NOGAMI
AU - Yumi SAKEMI
AU - Hidehiro KATO
AU - Masataka AKANE
AU - Yoshitaka MORIKAWA
PY - 2009
DO - 10.1587/transfun.E92.A.1859
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 8
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - August 2009
AB - 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.
ER -