Several methods for finding a basis conversion matrix between two different bases in an extension field have been proposed. Among them, the one based on Gauss period normal basis (GNB) is on average the most efficient. However, since it needs to construct a certain tower field , some inefficient cases in which the towering degree becomes large have been reported. This paper first determines that such inefficient cases are caused by the GNB condition. In order to overcome this inefficiency, we propose a method that does not use any GNB in the target extension field , but instead uses a certain polynomial basis in derived by a certain small cyclic group in . This causes re- laxation of the condition for the towering degree . In addition, our experimental results show that the proposed method substantially accelerates the computation time for finding a basis conversion matrix.

Recently, efficient pairings such as optimal-ate, R-ate, and Xate pairings have been proposed. On the other hand, some pairing-based cryptographic protocols need several pairing calculations for one procedure. Thus, multi-pairing technique will be efficiently applied. This paper optimizes Xate pairing for multi-pairing and then evaluates its efficiency with comparing to the other efficient pairings. Then, it is shown that the multi-pairing with the optimized Xate pairing is the most efficient.