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  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E92-A   No.1   pp.182-189
Publication Date: 2009/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E92.A.182
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Mathematics
Ate pairing,  BN curve,  scalar multiplication,  Frobenius mapping,  twisted subfield computation,  

Full Text: PDF(574.7KB)>>
Buy this Article

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 (Fp2) instead of doing on the original curve E(Fp12), we at first show sextic twisted subfield Frobenius mapping (ST-SFM) in (Fp2). 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.