Scalar Multiplication Using Frobenius Expansion over Twisted Elliptic Curve for Ate Pairing Based Cryptography

Yasuyuki NOGAMI, Yumi SAKEMI, Takumi OKIMOTO, Kenta NEKADO, Masataka AKANE, Yoshitaka MORIKAWA

Summary :

For ID-based cryptography, not only pairing but also scalar multiplication must be efficiently computable. In this paper, we propose a scalar multiplication method on the circumstances that we work at Ate pairing with Barreto-Naehrig (BN) curve. Note that the parameters of BN curve are given by a certain integer, namely mother parameter. Adhering the authors' previous policy that we execute scalar multiplication on subfield-twisted curve (F_p²) instead of doing on the original curve E(F_p¹²), we at first show sextic twisted subfield Frobenius mapping (ST-SFM) in (F_p²). On BN curves, note is identified with the scalar multiplication by p. However a scalar is always smaller than the order r of BN curve for Ate pairing, so ST-SFM does not directly applicable to the above circumstances. We then exploit the expressions of the curve order r and the characteristic p by the mother parameter to derive some radices such that they are expressed as a polynomial of p. Thus, a scalar multiplication [s] can be written by the series of ST-SFMs . In combination with the binary method or multi-exponentiation technique, this paper shows that the proposed method runs about twice or more faster than plain binary method.

• Publication: IEICE TRANSACTIONS on Fundamentals Vol.E92-A No.1 pp.182-189
• Publication Date: 2009/01/01
• Online ISSN: 1745-1337
• DOI: 10.1587/transfun.E92.A.182
• Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
• Category: Mathematics

Authors

Yasuyuki NOGAMI
Yumi SAKEMI
Takumi OKIMOTO
Kenta NEKADO
Masataka AKANE
Yoshitaka MORIKAWA

Keyword

Ate pairing,  BN curve,  scalar multiplication,  Frobenius mapping,  twisted subfield computation