Constructing Pairing-Friendly Elliptic Curves Using Global Number Fields

Efficient implementation of pairing-based cryptography requires construction of a pairing-friendly curve and its corresponding twisted curve. In this paper, we give a formula which determines the twisted curve. The formula are obtained by using technique in the algebraic number theory such as the complex multiplication theory. Applying the formula, we present an easy method for constructing pairing-friendly curves for BN-family. In fact, our method does not require the process of elliptic curve construction and finite field construction, but only requires searching an integer satisfying some conditions. Using our construction method, we implemented an optimal ate pairing for BN-family which is usable at various security levels, and investigated the time efficiency of the pairing computation for various security levels.