Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing

Yumi Sakemi; Shoichi Takeuchi; Yasuyuki Nogami; Yoshitaka Morikawa

doi:10.1007/978-3-642-14423-3_4

Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing

Yumi Sakemi, Shoichi Takeuchi, Yasuyuki Nogami, Yoshitaka Morikawa

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Citations (Scopus)

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 . On the other hand, the twisted Ate pairing requires 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 proposal 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 attained by the most efficient Ate pairings.

Original language	English
Title of host publication	Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers
Pages	47-64
Number of pages	18
DOIs	https://doi.org/10.1007/978-3-642-14423-3_4
Publication status	Published - Jul 20 2010
Event	12th International Conference on Information Security and Cryptology, ICISC 2009 - Seoul, Korea, Republic of Duration: Dec 2 2009 → Dec 4 2009

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5984 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	12th International Conference on Information Security and Cryptology, ICISC 2009
Country/Territory	Korea, Republic of
City	Seoul
Period	12/2/09 → 12/4/09

Keywords

Frobenius map
Miller's algorithm
multi-pairing
thread computing
twisted Ate pairing

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-14423-3_4

Cite this

Sakemi, Y., Takeuchi, S., Nogami, Y., & Morikawa, Y. (2010). Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing. In Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers (pp. 47-64). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS). https://doi.org/10.1007/978-3-642-14423-3_4

Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing. / Sakemi, Yumi; Takeuchi, Shoichi; Nogami, Yasuyuki et al.
Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. p. 47-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5984 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sakemi, Y, Takeuchi, S, Nogami, Y & Morikawa, Y 2010, Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing. in Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5984 LNCS, pp. 47-64, 12th International Conference on Information Security and Cryptology, ICISC 2009, Seoul, Korea, Republic of, 12/2/09. https://doi.org/10.1007/978-3-642-14423-3_4

Sakemi Y, Takeuchi S, Nogami Y, Morikawa Y. Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing. In Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. p. 47-64. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-14423-3_4

Sakemi, Yumi ; Takeuchi, Shoichi ; Nogami, Yasuyuki et al. / Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing. Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers. 2010. pp. 47-64 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{665d1cf2dc4f4d1184794bdce23ad637,

title = "Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing",

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 . On the other hand, the twisted Ate pairing requires 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 proposal 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 attained by the most efficient Ate pairings.",

keywords = "Frobenius map, Miller's algorithm, multi-pairing, thread computing, twisted Ate pairing",

author = "Yumi Sakemi and Shoichi Takeuchi and Yasuyuki Nogami and Yoshitaka Morikawa",

year = "2010",

month = jul,

day = "20",

doi = "10.1007/978-3-642-14423-3_4",

language = "English",

isbn = "3642144225",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "47--64",

booktitle = "Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers",

note = "12th International Conference on Information Security and Cryptology, ICISC 2009 ; Conference date: 02-12-2009 Through 04-12-2009",

}

TY - GEN

T1 - Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing

AU - Sakemi, Yumi

AU - Takeuchi, Shoichi

AU - Nogami, Yasuyuki

AU - Morikawa, Yoshitaka

PY - 2010/7/20

Y1 - 2010/7/20

N2 - 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 . On the other hand, the twisted Ate pairing requires 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 proposal 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 attained by the most efficient Ate pairings.

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 . On the other hand, the twisted Ate pairing requires 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 proposal 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 attained by the most efficient Ate pairings.

KW - Frobenius map

KW - Miller's algorithm

KW - multi-pairing

KW - thread computing

KW - twisted Ate pairing

UR - http://www.scopus.com/inward/record.url?scp=77954576003&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77954576003&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14423-3_4

DO - 10.1007/978-3-642-14423-3_4

M3 - Conference contribution

AN - SCOPUS:77954576003

SN - 3642144225

SN - 9783642144226

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 47

EP - 64

BT - Information Security and Cryptology - ICISC 2009 - 12th International Conference, Revised Selected Papers

T2 - 12th International Conference on Information Security and Cryptology, ICISC 2009

Y2 - 2 December 2009 through 4 December 2009

ER -

Accelerating twisted ate pairing with frobenius map, small scalar multiplication, and multi-pairing

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this