An Improvement of Twisted Ate Pairing Efficient for Multi-Pairing and Thread Computing
Summary :
In the case of Barreto-Naehrig pairing-friendly curves of embedding degree 12 of order r, recent efficient Ate pairings such as R-ate, optimal, and Xate pairings achieve Miller loop lengths of(1/4) ⌊log2 r⌋. On the other hand, the twisted Ate pairing requires (3/4) ⌊log2 r⌋ loop iterations, and thus is usually slower than the recent efficient Ate pairings. This paper proposes an improved twisted Ate pairing using Frobenius maps and a small scalar multiplication. The proposed idea splits the Miller's algorithm calculation into several independent parts, for which multi-pairing techniques apply efficiently. The maximum number of loop iterations in Miller's algorithm for the proposed twisted Ate pairing is equal to the (1/4) ⌊log2 r ⌋ attained by the most efficient Ate pairings.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.6 pp.1356-1367
- Publication Date
- 2011/06/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E94.A.1356
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Yumi SAKEMI, Yasuyuki NOGAMI, Shoichi TAKEUCHI, Yoshitaka MORIKAWA, "An Improvement of Twisted Ate Pairing Efficient for Multi-Pairing and Thread Computing" in IEICE TRANSACTIONS on Fundamentals,
vol. E94-A, no. 6, pp. 1356-1367, June 2011, doi: 10.1587/transfun.E94.A.1356.
Abstract: In the case of Barreto-Naehrig pairing-friendly curves of embedding degree 12 of order r, recent efficient Ate pairings such as R-ate, optimal, and Xate pairings achieve Miller loop lengths of(1/4) ⌊log2 r⌋. On the other hand, the twisted Ate pairing requires (3/4) ⌊log2 r⌋ loop iterations, and thus is usually slower than the recent efficient Ate pairings. This paper proposes an improved twisted Ate pairing using Frobenius maps and a small scalar multiplication. The proposed idea splits the Miller's algorithm calculation into several independent parts, for which multi-pairing techniques apply efficiently. The maximum number of loop iterations in Miller's algorithm for the proposed twisted Ate pairing is equal to the (1/4) ⌊log2 r ⌋ attained by the most efficient Ate pairings.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.1356/_p
Copy
@ARTICLE{e94-a_6_1356,
author={Yumi SAKEMI, Yasuyuki NOGAMI, Shoichi TAKEUCHI, Yoshitaka MORIKAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Improvement of Twisted Ate Pairing Efficient for Multi-Pairing and Thread Computing},
year={2011},
volume={E94-A},
number={6},
pages={1356-1367},
abstract={In the case of Barreto-Naehrig pairing-friendly curves of embedding degree 12 of order r, recent efficient Ate pairings such as R-ate, optimal, and Xate pairings achieve Miller loop lengths of(1/4) ⌊log2 r⌋. On the other hand, the twisted Ate pairing requires (3/4) ⌊log2 r⌋ loop iterations, and thus is usually slower than the recent efficient Ate pairings. This paper proposes an improved twisted Ate pairing using Frobenius maps and a small scalar multiplication. The proposed idea splits the Miller's algorithm calculation into several independent parts, for which multi-pairing techniques apply efficiently. The maximum number of loop iterations in Miller's algorithm for the proposed twisted Ate pairing is equal to the (1/4) ⌊log2 r ⌋ attained by the most efficient Ate pairings.},
keywords={},
doi={10.1587/transfun.E94.A.1356},
ISSN={1745-1337},
month={June},}
Copy
TY - JOUR
TI - An Improvement of Twisted Ate Pairing Efficient for Multi-Pairing and Thread Computing
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1356
EP - 1367
AU - Yumi SAKEMI
AU - Yasuyuki NOGAMI
AU - Shoichi TAKEUCHI
AU - Yoshitaka MORIKAWA
PY - 2011
DO - 10.1587/transfun.E94.A.1356
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2011
AB - In the case of Barreto-Naehrig pairing-friendly curves of embedding degree 12 of order r, recent efficient Ate pairings such as R-ate, optimal, and Xate pairings achieve Miller loop lengths of(1/4) ⌊log2 r⌋. On the other hand, the twisted Ate pairing requires (3/4) ⌊log2 r⌋ loop iterations, and thus is usually slower than the recent efficient Ate pairings. This paper proposes an improved twisted Ate pairing using Frobenius maps and a small scalar multiplication. The proposed idea splits the Miller's algorithm calculation into several independent parts, for which multi-pairing techniques apply efficiently. The maximum number of loop iterations in Miller's algorithm for the proposed twisted Ate pairing is equal to the (1/4) ⌊log2 r ⌋ attained by the most efficient Ate pairings.
ER -
English
