Fast Ate Pairing Computation of Embedding Degree 12 Using Subfield-Twisted Elliptic Curve

Masataka AKANE; Yasuyuki NOGAMI; Yoshitaka MORIKAWA

doi:10.1587/transfun.E92.A.508

Fast Ate Pairing Computation of Embedding Degree 12 Using Subfield-Twisted Elliptic Curve

Masataka AKANE, Yasuyuki NOGAMI, Yoshitaka MORIKAWA

Full Text Views

0

Cite this

Summary :

This paper presents implementation techniques of fast Ate pairing of embedding degree 12. In this case, we have no trouble in finding a prime order pairing friendly curve E such as the Barreto-Naehrig curve y²=x³+a, a∈F_p. For the curve, an isomorphic substitution from G₂ ⊂ E(F_p¹² into G'₂ in subfield-twisted elliptic curve E'(F_p²) speeds up scalar multiplications over G₂ and wipes out denominator calculations in Miller's algorithm. This paper mainly provides about 30% improvement of the Miller's algorithm calculation using proper subfield arithmetic operations. Moreover, we also provide the efficient parameter settings of the BN curves. When p is a 254-bit prime, the embedding degree is 12, and the processor is Pentium4 (3.6 GHz), it is shown that the proposed algorithm computes Ate pairing in 13.3 milli-seconds including final exponentiation.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.2 pp.508-516

Publication Date: 2009/02/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E92.A.508

Type of Manuscript: PAPER

Category: Cryptography and Information Security

Cite this

Copy

Masataka AKANE, Yasuyuki NOGAMI, Yoshitaka MORIKAWA, "Fast Ate Pairing Computation of Embedding Degree 12 Using Subfield-Twisted Elliptic Curve" in IEICE TRANSACTIONS on Fundamentals, vol. E92-A, no. 2, pp. 508-516, February 2009, doi: 10.1587/transfun.E92.A.508.
Abstract: This paper presents implementation techniques of fast Ate pairing of embedding degree 12. In this case, we have no trouble in finding a prime order pairing friendly curve E such as the Barreto-Naehrig curve y²=x³+a, a∈F_p. For the curve, an isomorphic substitution from G₂ ⊂ E(F_p¹² into G'₂ in subfield-twisted elliptic curve E'(F_p²) speeds up scalar multiplications over G₂ and wipes out denominator calculations in Miller's algorithm. This paper mainly provides about 30% improvement of the Miller's algorithm calculation using proper subfield arithmetic operations. Moreover, we also provide the efficient parameter settings of the BN curves. When p is a 254-bit prime, the embedding degree is 12, and the processor is Pentium4 (3.6 GHz), it is shown that the proposed algorithm computes Ate pairing in 13.3 milli-seconds including final exponentiation.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E92.A.508/_p

Copy

@ARTICLE{e92-a_2_508,
author={Masataka AKANE, Yasuyuki NOGAMI, Yoshitaka MORIKAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Fast Ate Pairing Computation of Embedding Degree 12 Using Subfield-Twisted Elliptic Curve},
year={2009},
volume={E92-A},
number={2},
pages={508-516},
abstract={This paper presents implementation techniques of fast Ate pairing of embedding degree 12. In this case, we have no trouble in finding a prime order pairing friendly curve E such as the Barreto-Naehrig curve y²=x³+a, a∈F_p. For the curve, an isomorphic substitution from G₂ ⊂ E(F_p¹² into G'₂ in subfield-twisted elliptic curve E'(F_p²) speeds up scalar multiplications over G₂ and wipes out denominator calculations in Miller's algorithm. This paper mainly provides about 30% improvement of the Miller's algorithm calculation using proper subfield arithmetic operations. Moreover, we also provide the efficient parameter settings of the BN curves. When p is a 254-bit prime, the embedding degree is 12, and the processor is Pentium4 (3.6 GHz), it is shown that the proposed algorithm computes Ate pairing in 13.3 milli-seconds including final exponentiation.},
keywords={},
doi={10.1587/transfun.E92.A.508},
ISSN={1745-1337},
month={February},}

Copy

TY - JOUR
TI - Fast Ate Pairing Computation of Embedding Degree 12 Using Subfield-Twisted Elliptic Curve
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 508
EP - 516
AU - Masataka AKANE
AU - Yasuyuki NOGAMI
AU - Yoshitaka MORIKAWA
PY - 2009
DO - 10.1587/transfun.E92.A.508
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E92-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2009
AB - This paper presents implementation techniques of fast Ate pairing of embedding degree 12. In this case, we have no trouble in finding a prime order pairing friendly curve E such as the Barreto-Naehrig curve y²=x³+a, a∈F_p. For the curve, an isomorphic substitution from G₂ ⊂ E(F_p¹² into G'₂ in subfield-twisted elliptic curve E'(F_p²) speeds up scalar multiplications over G₂ and wipes out denominator calculations in Miller's algorithm. This paper mainly provides about 30% improvement of the Miller's algorithm calculation using proper subfield arithmetic operations. Moreover, we also provide the efficient parameter settings of the BN curves. When p is a 254-bit prime, the embedding degree is 12, and the processor is Pentium4 (3.6 GHz), it is shown that the proposed algorithm computes Ate pairing in 13.3 milli-seconds including final exponentiation.
ER -