Speeding up Pairing Computation Using Non-adjacent Form and ELM Method

The bilinear pairings such as Weil pairing and Tate pairing on elliptic curves have recently found many applications in cryptography. The first efficient algorithm for computing pairing was originally proposed by Miller and much subsequent research has been directed at many different aspects in order to improve efficiency. In 2003, Eisentrager, Lauter and Montgomery proposed a new point-double-addition method to speed up elliptic curve arithmetic computation and obtained a 7.8% performance improvement of the Miller algorithm of a general elliptic curve. In 2006, Blake et al. proposed a new concept based on the conjugate of a line to reduce the total number of lines in the Miller algorithm. In this paper we propose an enhancement of Eisentrager et al.'s algorithm for computing pairings. Our enhancement can further speed up the pairing computation by 5.9%.