Boneh et al. proposed the new idea of pairing-based cryptography by using the composite order group instead of prime order group. Recently, many cryptographic schemes using pairings of composite order group were proposed. Miller's algorithm is used to compute pairings, and the time of computing the pairings depends on the cost of calculating the Miller loop. As a method of speeding up calculations of the pairings of prime order, the number of iterations of the Miller loop can be reduced by choosing a prime order of low Hamming weight. However, it is difficult to choose a particular composite order that can speed up the pairings of composite order. Kobayashi et al. proposed an efficient algorithm for computing Miller's algorithm by using a window method, called Window Miller's algorithm. We can compute scalar multiplication of points on elliptic curves by using a window hybrid binary-ternary form (w-HBTF). In this paper, we propose a Miller's algorithm that uses w-HBTF to compute Tate pairing efficiently. This algorithm needs a precomputation both of the points on an elliptic curve and rational functions. The proposed algorithm was implemented in Java on a PC and compared with Window Miller's Algorithm in terms of the time and memory needed to make their precomputed tables. We used the supersingular elliptic curve y2=x3+x with embedding degree 2 and a composite order of size of 2048-bit. We denote w as window width. The proposed algorithm with w=6=2·3 was about 12.9% faster than Window Miller's Algorithm with w=2 although the memory size of these algorithms is the same. Moreover, the proposed algorithm with w=162=2·34 was about 12.2% faster than Window Miller's algorithm with w=7.

This paper considers the normalization of Miller functions for computing “point-evaluation” pairings on an elliptic curve E over a finite field Fq, where the characteristic of Fq is neither 2 nor 3. It is shown that the normalized Miller functions for computing point-evaluation pairings on G2G1 when (i) the embedding degree k is even, or (ii) 3|k and E/Fq(q ≡ (1 mod 3)) is a curve of the form Y2=X3+b. Thus, there is no need to consider the normalization for computing pairings on many pairing-friendly elliptic curves.

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.

It is said that the lower bound of the number of iterations of Miller's algorithm for pairing calculation is log 2r/(k), where () is the Euler's function, r is the group order, and k is the embedding degree. Ate pairing reduced the number of the loops of Miller's algorithm of Tate pairing from ⌊log 2r⌋ to ⌊ log 2(t-1)⌋, where t is the Frobenius trace. Recently, it is known to systematically prepare a pairing-friendly elliptic curve whose parameters are given by a polynomial of integer variable "χ." For such a curve, this paper gives integer variable χ-based Ate (Xate) pairing that achieves the lower bound. In the case of the well-known Barreto-Naehrig pairing-friendly curve, it reduces the number of loops to ⌊log 2χ⌋. Then, this paper optimizes Xate pairing for Barreto-Naehrig curve and shows its efficiency based on some simulation results.